Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://dfgm.math.msu.su/files/papers-sym/conder.pdf Äàòà èçìåíåíèÿ: Fri Feb 29 14:49:46 2008 Äàòà èíäåêñèðîâàíèÿ: Sat Apr 9 22:33:39 2016 Êîäèðîâêà:

Journal of Combinatorial Theory, Series B 81, 224 242 ( 2001 ) doi:10.1006ájctb.2000.2008, available online at http:ááwww.idealibrary.com on

Determination of all Regular Maps of Small Genus
Marston Conder and Peter Dobcsanyi
Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand E-mail: conderämath.auckland.ac.nz; peteräscitec.auckland.ac.nz Received June 25, 1999

Complete lists are given of all reflexible orientable regular maps of genus 2 to 15, all non-orientable regular maps of genus 4 to 30, and all ( orientable ) rotary but chiral ( irreflexible ) maps of genus 2 to 15 inclusive. On each list the maps are classified according to genus and type ( viz [p, q] where every face is incident with p edges and every vertex is incident with q edges ). The complete lists were determined with the help of a parallel program which finds all normal subgroups of low index in a finitely-presented group. 2001 Academic Press

1. INTRODUCTION A map is a 2-cell embedding of a connected graph ( or multigraph ) into a closed surface without boundary. Such a map M is composed of a vertexset V = V( M ), an edge-set E = E( M ), and a set of faces which we will denote by F = F ( M ). The map is called orientable or non-orientable according to whether the underlying surface ( on which the graph is embedded ) is orientable or non-orientable. The faces of M are the simplyconnected components of the space obtained by removing the embedded graph from the surface; alternatively, in the orientable case, they can be defined more directly by considering just the underlying graph together with a ``rotation'' at each vertex ( see [2]). Associated also with any map is a set of darts, or arcs, which are the incident vertex-edge pairs ( v, e )# V_E. Each dart is made up of two blades, one corresponding to each face containing the edge e ( except in degenerate situations where an edge lies in just one face, but these will not concern us here. ) An automorphism of a map M is a permutation of its blades, preserving the properties of incidence, and as usual these form a group under composition, called the automorphism group of the map, and denoted by 224
0095-8956á01 35.00
Copyright 2001 by Academic Press All rights of reproduction in any form reserved.


REGULAR MAPS OF SMALL GENUS

225

Aut M. From connectedness of the underlying graph, it follows that every automorphism is uniquely determined by its effect on any blade, and hence the number of automorphisms of M is bounded above by the number of blades, or equivalently, | Aut M | 4 | E |. Now if there exist automorphisms R and S with the property that R cyclically permutes the consecutive edges of some face f ( in single steps around f ), and S cyclically permutes the consecutive edges incident to some vertex v of f ( in single steps around v ), then following Wilson [ 10 ] we may call M a rotary map. Under more currently acceptable terminology, M is also called a regular map ( in the sense of Brahana [ 4 ] ). In this case ( again by connectedness ) the group Aut M acts transitively on the vertices, on edges, and on faces of M, and it follows that all the faces are bordered by the same number of edges, say p, while all the vertices have the same degree, say q. The pair [p, q] is known as the type of the regular map M. Note that the topological dual of M, denoted by M * and obtainable by defining V( M *) = F ( M ), E( M *) = E( M ) and F ( M *) = V( M ) and taking the same relations of incidence, will also be regular, with the same automorphism group as M and of type [q, p]. Note also that R and S may be chosen ( replacing one of them by its inverse if necessary ) so that the automorphism RS interchanges the vertex v with one of its neighbours along an edge e ( on the border of f ), interchanging f with the other face containing e in the process. The three automorphisms R, S and RS may thus be viewed as rotations which satisfy the relations R p = S q =( RS ) 2 =1. If a rotary map M admits also an automorphism a which ( like RS ) ``flips'' the edge e but ( unlike RS ) preserves the face f, then we say the regular map M is reflexible. This automorphism a is may be thought of geometrically as a reflection, about an axis passing through the midpoints of the edge e and the face f. Similarly, the automorphisms b = aR and c = bS may also be thought of as reflections, and the following relations are satisfied: a 2 = b 2 = c 2 =( ab ) p =( bc ) q =( ca ) 2 = 1. Also in this case, Aut M is transitive ( indeed regular ) on blades, and can be generated by the three reflections a, b and c. If the map M is orientable, then the elements R = ab and S = bc generate a normal subgroup of index 2 in Aut M, consisting of all elements expressible as a word of even length in [a, b, c], called the rotation subgroup Aut +M. In this case the elements of Aut +M are precisely those automorphisms which preserve the orientation of the underlying surface, while all those in Aut M "Aut +M are orientation-reversing. In the non-orientable case, however, there are no true reflections: every ``reflection'' is a product of rotations. In particular, each of a, b and c is expressible as a word in the rotations R and S, and hence (R, S) = (ab, bc ) has index 1 in Aut M.


226

CONDER AND DOBCSANYI

On the other hand, if no such automorphism a exists, then the rotary map M is called chiral, and its automorphism group can be generated by the rotations R and S. Chiral maps are necessarily orientable. Also chiral maps occur in opposite pairs, with one member of each pair obtainable from the other by reflection. Further details and some historical background may be found in [ 1, 2, 7, 9, 10 ]. The genus of a map M is defined as the genus g of the surface on which M is embedded, and is given by the usual formula in terms of the Euler characteristic: /( M )= | V |& | E |+ | F |=

{

2& 2g 2& g

if M is orientable if M is non-orientable.

For regular maps of type [p, q], counting the number of blades containing a given edge e yields | Aut M |= 2 | E | when the regular map M is chiral, while | Aut M |= 4 | E | when M is reflexible, and also in either case, counting the number of darts incident with a given vertex, edge or face gives the well known identities q | V |= 2 | E |= p | F | . These together with the formula above make the calculation of the genus straightforward: g = g( M ) | Aut M | ( 1á8& 1á4p &1á4q )+1 = | Aut M | ( 1á4& 1á2p &1á2q )+1 | Aut M | ( 1á4& 1á2p &1á2q )+2

{

if M is orientable and reflexible if M is orientable but chiral if M is non-orientable.

In this paper we describe the determination of all regular maps of small genus, using the above background information and a program to systematically enumerate all possibilities for the automorphism group. Specifically, we provide complete lists of the following: v all reflexible orientable regular maps of genus between 2 and 15 inclusive, v all chiral regular maps of genus between 2 and 15 inclusive, and v all non-orientable regular maps of genus between 3 and 30 inclusive. Orientable regular maps of genus 0 ( spherical maps ) and those of genus 1 ( toroidal maps ) are known and well understood see [ 7, 9 ]. The lists we produce now considerably extend the current state of knowledge. Indeed at the time of writing we understand that orientable regular maps have been classified for genus up to only 7 ( see [ 1, 7 ] for example ), and there has been no serious attempt to classify non-orientable regular maps of small genus at all.


REGULAR MAPS OF SMALL GENUS

227

Further background is given in Section 2, including the connection with group presentations which is fundamental to our approach, and a brief description of the computational methods involved. Further details are available in [ 5, 8 ]. The resulting complete lists are produced in Section 3, and a few concluding remarks are offered in Section 4.

2. FURTHER BACKGROUND As follows from the sort of analysis provided earlier, the rotation group Aut + M of any rotary map M of type [p, q] is a homomorphic image of the ( p, q, 2 ) triangle group 2 = 2( p, q, 2 ) = ( u, v | u p = v q =( uv ) 2 =1 ) , via some homomorphism taking u to R and v to S; in particular, this homomorphism from 2 onto Aut + M is non-degenerate, meaning that the orders of the two generators and their product are preserved. Conversely, any non-degenerate homomorphism from 2( p, q, 2 ) to a finite group G yields a rotary map M of type [p, q] on which G acts as rotation group. In fact if R and S are the images in G of the generators u and v of 2( p, q, 2 ), then the vertices, edges and faces of M may be taken as the ( right ) cosets in G of the subgroups V = (S ) , E = (RS ) and F = (R ) respectively, with incidence defined by non-empty intersection. The group G acts by right multiplication, and the three subgroups V, E and F then become the stabilizers of some mutually incident vertex v, edge e and face f respectively. This correspondence also extends to reflexible maps: the automorphism group of any reflexible regular map M of type [p, q] is a non-degenerate homomorphic image of the extended ( p, q, 2 ) triangle group 2*= 2*( p, q, 2 ) = (t, u, v | t 2 =( ut ) 2 =( tv ) 2 = u p = v q =( uv ) 2 =1 ) , via some homomorphism taking u to R and v to S, and t to the reflection b = aR described earlier; and conversely, any non-degenerate homomorphism from 2*( p, q, 2 ) to a finite group G yields a reflexible regular map M of type [p, q] on which G acts as automorphism group. Here the vertices, edges and faces of M may be taken as the ( right ) cosets in G of the subgroups V = (b, c) , E = (a, c) and F = (a, b) respectively, again with incidence defined by non-empty intersection, where a, b and c are the images of ut, t and tv respectively. Also the corresponding map M is orientable if and only if the subgroup (ab, bc ) of G = Aut M has index 2 in G. Now using this correspondence between regular maps and generators for their automorphism groups, we can set about finding regular maps on surfaces of up to given genus by determining groups with the appropriate properties or more specifically, non-degenerate finite homomorphic images of the groups 2( p, q, 2 ) and 2*( p, q, 2 ). To do this, rather than consider all


228

CONDER AND DOBCSANYI

possibilities for the type [p, q] for ( up to ) given genus, we determine all suitable images of the following two finitely-presented groups: 8 = (u, v |( uv ) 2 =1 ) and 8*= (t, u, v | t 2 =( ut ) 2 =( tv ) 2 =( uv ) 2 =1 ) .

If G is a finite homomorphic image of 8*, via some homomorphism which preserves the orders of t, ut, vt and uv, then if p and q denote the orders of the images in G of u and v respectively, then there exists a regular map M of type [p, q] on which the group G acts as automorphism group. This map M is non-orientable if and only if the image of t lies in the subgroup generated by the images of u and v, or equivalently, since t inverts each of u and v by conjugation, if and only if there exists some relation involving the images of u, v and t in which the number of occurrences of t is odd. Otherwise ( when there is no such relation ) the map is orientable and reflexible. Further, once the orders of G and of the images of u and v are known, the genus of M can be calculated using the formula given in the Introduction. Hence the problem of finding all reflexible regular maps is reduced to determining finite factor groups of 8* ( and examining their properties ). For example, the symmetric group S 4 of degree 4 is obtainable as a factor group of 8* via a homomorphism taking t to ( 1, 2 ), u to ( 1, 2, 3 ), and v to ( 1, 2, 4 ), and so is the automorphism group of a reflexible regular map of type [ 3, 3 ]. As the images of u and v generate the alternating group A 4 , the map is orientable, and the genus is 24( 1á8& 1á12 & 1á12 ) + 1 = 0. Of course this is nothing more than the tetrahedral graph embedded on the sphere, however it serves to illustrate the point. Similarly, S 4 is obtainable as a factor group of 8* via a different homomorphism taking t to ( 1, 2 ), u to ( 1, 2, 3 ), and v to ( 1, 3, 2, 4 ), and so is also the automorphism group of reflexible regular map of type [ 3, 4 ]. As the images of u and v generate S4 , the map is non-orientable, and its genus is 24( 1á4& 1á6& 1á8 ) +2 =1. More generally, suppose G is the automorphism group of a reflexible regular map M of genus g. If M is orientable then g &1 = | G | ( 1á8&1á4p & 1á4q ), and so for given ( orientable ) genus g > 1 the largest possible order for G is achieved when ( 1á8&1á4p &1á4q ) takes its minimum possible value, namely 1á168, when [p, q] = [ 3, 7 ]. Rearranging, this gives | G | 168( g &1) for g > 1. On the other hand, if M is non-orientable then g &2 =| G | ( 1á4& 1á2p &1á2q ), and so for given ( non-orientable ) genus g > 2 the largest possible order for G is achieved when ( 1á4& 1á2p &1á2q ) takes its minimum possible value, namely 1á84, again when [p, q] = [ 3, 7 ], but this time we find | G | 84( g & 2 ) for g > 2. Thus to find reflexible orientable regular maps of genus 2 to 15, we need to consider finite factor groups of 8* of order up to 168( 15 & 1 ) = 2352, and as also 2352 = 84( 30 & 2 ), the same information can be used to determine non-orientable regular maps of genus 3 to 30.


REGULAR MAPS OF SMALL GENUS

229

Now the problem of determining all finite factor groups of a given finitelypresented group 4 of up to some prescribed order N is equivalent to finding all normal subgroups of index up to N in 4, and the development and implementation of an algorithm for doing this have been described in detail in [ 5 ]. Our algorithm is an adaptation of one due to Charles Sims and others for finding conjugacy classes of all subgroups of up to a given index. To find a representative of each such class of subgroups, the standard algorithm uses a back-track search through a tree, with nodes at level k corresponding to certain subgroups generated by k elements. The search begins ( at level 0 ) with the identity subgroup, generated by the empty set ,, and successively adjoins and removes elements to and from the generating set for the subgroup, on a last-in first-out basis. Standard techniques of coset enumeration are used at each node to determine how to proceed. In our adaptation, the additional subgroup generators are treated as relators ( representatives of conjugacy classes of elements generating a normal subgroup ), rather than simply elements which usually generate a subgroup that is not normal. In practice the application of this algorithm to finding normal subgroups of index up to 2352 in 8* takes an excessive amount of computing time, and produces a significant number of examples corresponding to maps of much higher genus ( but not all such examples ), so we split the problem into four manageable sub-problems as follows: ( a ) finding normal subgroups of the group 2*( 3, 7, 2 ) of index up to 2352, ( b ) finding normal subgroups of the group (t, u, v | t 2 =( ut ) 2 =( tv ) = u =( uv ) 2 =1 ) of index up to 1344,
3 2

( c ) finding normal subgroups of the group (t, u, v | t 2 =( ut ) 2 =( tv ) = u 4 =( uv ) 2 =1 ) of index up to 1120, (d) finding normal subgroups of 8* of index up to 560.

2

The rationale behind this may be explained as follows. First, by replacing a map by its dual if necessary, we may assume each regular map has type [p, q] where 3 p q (and 1áp +1áq <1á2 for orientable genus g >1 or non-orientable genus g > 2 ). Next if the type [p, q] of the regular map M is not [ 3, 7 ], then the largest possible order for its automorphism group is 96( g &1) if M is orientable, or 48( g &2 ) if M is non-orientable, and hence the maximum index can be reduced to 96( 15 & 1 ) = 1344 = 48( 30 & 2 ) when [p, q] { [ 3, 7 ]. Similarly if 4 p q, then the largest possible order for Aut M is 80( g &1 ) if M is orientable or 40( g &2 ) if M is non-orientable ( with the maximum achieved in both cases when [p, q] = [ 4, 5 ] ), and hence the maximum index can be reduced to 80( 15 & 1 ) = 1120 = 40( 30 & 2 ) in this


230

CONDER AND DOBCSANYI

case. Finally if both p and q are at least 5, then the largest possible order for Aut M is 40( g &1 ) if M is orientable or 20( g &2 ) if M is non-orientable ( with the maximum achieved in both cases when [p, q] = [ 5, 5 ] ), and hence the maximum index can be reduced to 40( 15 & 1 ) = 560 = 20( 30 & 2 ) when 5 p q. The algorithm produces all normal subgroups of up to the specified index, giving a set of representatives of conjugacy classes of elements generating each one ( or equivalently a set of additional relators which yield the associated factor group when adjoined to the group's presentation ), along with a coset table indicating the natural permutation representation of the group on the cosets of the normal subgroup in each case. From the former it is a simple matter to determine whether or not the corresponding map is orientable ( by checking for any relator in which the generator ``t'' occurs an odd number of times ), and from the latter it is easy to determine the orders of the images of the generators, and hence the type of the map. Also using the coset table ( or associated permutation representation ), it is a simple matter to test whether the corresponding map is self-dual, by interchanging the columns ( or permutations ) corresponding to the generators u and v and checking whether or not the resulting coset table ( or permutation representation ) is equivalent to the original. If it is, then the map is self-dual, while on the other hand if they are not equivalent, then the map and its dual are distinct ( and one of them can then be eliminated ). The same sort of approach can be taken for chiral rotary maps. If G is a finite factor group of the group 8 = (u, v |( uv ) 2 =1 ) via some homomorphism which preserves the order of uv, and p and q denote the orders of the images of u and v in G, then there exists a rotary map M of type [p, q] on which the group G acts as rotation group. This map is chiral ( and then necessarily orientable) if and only if there exists no automorphism of G which inverts the images of each of u and v by conjugation, and once more the genus of M can be calculated using the formula given in the Introduction. In particular, if M is chiral then g &1 = | G | ( 1á4&1á2p &1á2q ), and so for given ( orientable) genus g > 1 the largest possible order for G is achieved when (1á4& 1á2p &1á2q ) takes its minimum possible value, namely 1á84, when [p, q] = [ 3, 7 ]. Rearranging, this gives | G | 84( g & 1 ) for g > 1. Thus to find chiral rotary maps of genus 2 to 15, we need to consider finite factor groups of 8 of order up to 84( 15 & 1 ) = 1176, or equivalently, all normal subgroups of index up to 1176 in 8. Again this can be split into subproblems in which the order of u is 3, 4 or arbitrary ( but at least 5 ), however the computations are much easier for given orientable genus than in the reflexible case. Chirality can be tested using the coset tables in a similar way to the duality test: simply replace the columns defining the actions of the generators u and


REGULAR MAPS OF SMALL GENUS

231

v by columns which give the actions of u &1 and v &1 respectively, and check whether the resulting coset table ( or permutation representation) is equivalent to the original. If it is, then the map is reflexible and so can be eliminated, while on the other hand if is not, then no reflection exists and so the map is chiral. ( Note: although this test can be used to show reflexibility, it does not give additional information about the reflections themselves, and in particular does not help with the question of orientability in the reflexible case. ) The computations were carried out on a distributed processing system using at times well over 100 separate processors ( the ``Kalaka'' system developed by the second author and described in his Ph.D. thesis [ 8 ] ). The following indicate the time taken for the longest branch of each computation: Computation Reflexible, type [ 3, 7 ] Reflexible, type [ 3, & ] Reflexible, type [ 4, & ] Reflexible, any type Chiral, type [ 3, 7 ] Chiral, type [ 3, & ] Chiral, type [ 4, & ] Chiral, any type Group ( 8* | u 3 = v 7 =1 ) ( 8* | u 3 =1 ) ( 8* | u 4 =1 ) 8* ( 8 | u 3 = v 7 =1 ) ( 8 | u 3 =1 ) ( 8 | u 4 =1 ) 8 Index 2352 1344 1120 560 1176 672 560 280 1 5 14 11 Time hour 57 minutes hours 1 minute hours 51 minutes hours 55 minutes 47 minutes 2 hours 8 minutes 5 hours 37 minutes 5 hours 35 minutes

3. RESULTS The results of our computations are summarised in the tables below. We give three separate tables: reflexible orientable maps ( Table I ), chiral rotary maps ( Table II ), and nonorientable regular maps ( Table III ). In each table the maps are classified according to their genus, and we give a label of the form Rg . i, Cg . i or Ng . i for the ith map of genus g in the respective list. Also for each map we give its type, the order of its automorphism group ( in the column headed ``Automs'' ), and the edge-multiplicities of the underlying graph of the map and its dual ( in the columns headed m V and m F ). The latter multiplicities are easily seen to be the orders of the normal cores of the subgroups generated by the vertex rotation S and the face rotation R respectively. The presence of an asterisk following the label of the map indicates that the map is self-dual. Finally for each we provide additional relators which are sufficient to define the automorphism group of the map in terms of canonical generators R and S for orientable maps, either reflexible or chiral, and also T ( replacing the reflection b = aR ) in the case of non-orientable maps.


232

CONDER AND DOBCSANYI TABLE I Orientable Reflexible Regular Maps of Genus 2 to 15

Map R2.1 R2.2 R2.3 R2.4 R2.5* R2.6* R3.1 R3.2 R3.3 R3.4 R3.5 R3.6 R3.7 R3.8* R3.9 R3.10* R3.11* R3.12* R4.1 R4.2 R4.3 R4.4 R4.5 R4.6* R4.7* R4.8 R4.9 R4.10 R4.11* R4.12* R5.1 R5.2 R5.3 R5.4 R5.5 R5.6 R5.7 R5.8 R5.9* R5.10* R5.11 R5.12*

Genus 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5

Type [ 3, [ 4, [ 4, [ 5, [ 6, [ 8, [ 3, [ 3, [ 3, [ 4, [ 4, [ 4, [ 4, [ 6, [ 7, [ 8, [ 8, [ 12, [ 3, [ 4, [ 4, [ 4, [ 4, [ 5, [ 6, [ 6, [ 6, [ 9, [ 10, [ 16, [ 3, [ 3, [ 4, [ 4, [ 4, [ 4, [ 4, [ 4, [ 5, [ 6, [ 6, [ 8, 8] 6] 8] 10 ] 6] 8] 7] 8] 12 ] 6] 8] 8] 12 ] 6] 14 ] 8] 8] 12 ] 12 ] 5] 6] 10 ] 16 ] 5] 6] 6] 12 ] 18 ] 10 ] 16 ] 8] 10 ] 5] 6] 8] 8] 12 ] 20 ] 5] 6] 15 ] 8]

Automs 96 48 32 20 24 16 336 192 96 96 64 64 48 48 28 32 32 24 144 240 144 80 64 120 72 72 48 36 40 32 384 240 320 192 128 128 96 80 160 96 60 64

m

V

m

F

Additional relators R 3, ( RS &3 ) 2 ( RS &1 ) 2, R 4, S 6 ( RS &1 ) 2, R 4, RS 3R [ R, S ], S 2R &3 [ R, S ], R 2S &4 [ R, S ], RS &3

2 3 8 10 6 8 1 1 4 2 4 4 12 2 14 8 8 12 3 1 1 5 16 1 3 2 12 18 10 16 1 2 1 1 2 2 6 20 1 2 15 4

1 2 2 5 6 8 1 1 1 1 1 2 2 2 7 8 8 12 1 1 1 2 2 1 3 3 3 9 10 16 1 1 1 1 1 1 2 2 1 2 3 4

&1

S

&1

R 3, S 7, ( RS &2 ) 4 R 3, S 8, ( S 2R &1 ) 3 R 3 , [ R, S 3 ] R 4, ( RS &2 ) 2, S 6 R 4 , [ R, S 2 ] ( RS &1 ) 2, R 4, S 8 ( RS &1 ) 2, R 4, RS 5R &1S R 2S 2R &1S &1, R 3S &3 [ R, S ], S 2R &5 R 2S &2 [ R, S ], R 4S &4 [ R, S ], R 3S &3

&1

R 3, ( S 2R &1 ) 3, [ R, S 4 ] R 4, S 5, ( RS &1RS &2 ) 2 R 4, S 6, [ RS, SR ] ( RS &1 ) 2, R 4, S 10 ( RS &1 ) 2, R 4, RS 7R &1S &1 R 5, S 5, ( RS &1 ) 3 ( RS &1 ) 2, R 6, S 6 [ R 2, S ], ( RS &2 ) 2, S 6 [ R 2, S ], [ R, S 2 ], R 2S &4 [ R, S ], S 4R &5 [ R, S ], R 4S &6 [ R, S ], R 3S &5 R 3, S 8, RS 4RS &2R &1S 2R &1S &2 R 3, ( RS &4 ) 2 R 4, S 5, ( RS &1 ) 4 R 4, S 6, ( RS &1 ) 4, RS 3RS &1R &1SR R 4, [ RS, SR ], ( RS &3 ) 2 R 4, RS &2RS &1R &2S &1, S 8 ( RS &1 ) 2, R 4, S 12 ( RS &1 ) 2, R 4, RS 9R &1S &1 R 5, S 5, [ RS, SR ] ( RS &2 ) 2, ( R 2S &1 ) 2, R 6 [ R 2, S ], ( RS &2 ) 2, R 2S 5 ( RS &1 ) 2, RS 3R &3S &1

&1

S

&1


REGULAR MAPS OF SMALL GENUS TABLE I Map R5.13* R5.14 R5.15* R5.16* R6.1 R6.2 R6.3 R6.4 R6.5 R6.6 R6.7 R6.8 R6.9* R6.10 R6.11 R6.12* R6.13* R7.1 R7.2 R7.3 R7.4 R7.5 R7.6 R7.7 R7.8 R7.9 R7.10* R7.11* R7.12* R8.1 R8.2 R8.3 R8.4 R8.5 R8.6 R8.7 R8.8 R8.9 R8.10* R8.11* R9.1 R9.2 Genus 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 9 9 Type [ 8, 8 [ 11, 2 [ 12, 1 [ 20, 2 [ 3, [ 4, [ 4, [ 4, [ 4, [ 5, [ 6, [ 6, [ 9, [ 10, [ 13, [ 14, [ 24, [ 3, [ 3, [ 4, [ 4, [ 4, [ 6, [ 6, [ 6, [ 15, [ 16, [ 16, [ 28, [ 3, [ 3, [ 4, [ 4, [ 6, [ 6, [ 8, [ 10, [ 17, [ 18, [ 32, ] 2] 2] 0] Automs 64 44 48 40 300 240 144 112 96 100 96 96 72 60 52 56 48 1008 288 128 128 112 108 96 84 60 64 64 56 672 672 144 128 120 96 96 80 68 72 64 384 640 m
V

233

( Continued ) m
F

Additional relators [ [ [ [ R R R R , S ], [ R, S 2 ], R 4S , S ], S 4R &7 , S ], R 6S &6 , S ], R 5S &5
2 &4

4 22 12 20 1 1 3 7 24 5 4 2 3 15 26 14 24 1 2 8 8 28 3 4 21 30 16 16 28 1 1 9 32 5 24 6 20 34 18 32 2 1

4 11 12 20 1 1 1 2 2 1 3 2 3 5 13 14 24 1 1 1 2 2 3 2 3 15 16 16 28 1 1 2 2 3 3 4 5 17 18 32 1 1

10 ] 6] 9] 14 ] 24 ] 10 ] 8] 8] 9] 15 ] 26 ] 14 ] 24 ] 7] 12 ] 16 ] 16 ] 28 ] 9] 12 ] 21 ] 30 ] 16 ] 16 ] 28 ] 8] 8] 18 ] 32 ] 10 ] 24 ] 12 ] 20 ] 34 ] 18 ] 32 ]

R 3, ( S 2R &1 ) 3, S 10 R 4, ( RS &1 ) 3, S 6 R 4, ( RS &2 ) 2, S 9 ( RS &1 ) 2, R 4, S 14 ( RS &1 ) 2, R 4, RS 11R &1S R 5 , [ R, S 2 ] ( RS &1 ) 2, R 6, S 8 ( R 2S &1 ) 2, R 6, R 3S 4 R 2S 2R &1S &1, S 3R &6 S 3R &2 [ R, S ], S 6R &7 [ R, S ], R 6S &8 [ R, S ], R 5S &7

&1

R 3, S 7, RS 3R &1S 3RS &2( R &1S 2 ) 2 R &1S R 3, RS &3RS &2R &1SR &1S &2 R 4, RS &2RS &1R &2S &1, RS 6R &1S &2 ( RS &1 ) 2, R 4, S 16 ( RS &1 ) 2, R 4, RS 13R &1S &1 [ R 2, S ], ( RS &2 ) 2, S 9 ( R 2S &1 ) 2, R 6, S &2RS &2R &2 [ R 2, S ], ( RS &2 ) 2, S 7R &2 [ R, S ], S 6R &9 [ R, S ], R 8S &8 [ R 2, S ], [ R, S 2 ], R 2S &6 [ R, S ], R 7S &7 R 3, S 8, ( RS &2 ) 4 R 3, S 8, [ RS, S 3RS &2 ] ( RS &1 ) 2, R 4, S 18 ( RS &1 ) 2, R 4, RS 15R &1S &1 ( RS &1 ) 2, R 6, S 10 [ R 2, S ], ( RS &2 ) 2, RS 7R &1S &1 ( RS &1 ) 2, R 8, RS 5R &3S &1 [ R 2, S ], [ R, S 2 ], R 3S &1RS &5 [ R, S ], S 8R &9 [ R, S ], R 8S &10 [ R, S ], R 7S &9 R 3, ( RS &5 ) 2, ( RS &2 ) 4 R 4, S 5, RS 2R &1S 2RS &1( R

&2

[ 3, 12 ] [ 4, 5 ]

&1

S)2 R

&1

S

&1


234

CONDER AND DOBCSANYI TABLE I ( Continued ) m
F

Map R9.3 R9.4 R9.5 R9.6 R9.7 R9.8 R9.9 R9.10 R9.11 R9.12 R9.13 R9.14* R9.15 R9.16 R9.17* R9.18* R9.19* R9.20 R9.21* R9.22* R9.23* R9.24 R9.25 R9.26* R9.27* R9.28* R9.29 R9.30 R9.31* R9.32* R10.1 R10.2 R10.3 R10.4 R10.5 R10.6 R10.7 R10.8 R10.9 R10.10 R10.11 R10.12 R10.13* R10.14*

Genus 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10

Type [ 4, [ 4, [ 4, [ 4, [ 4, [ 4, [ 4, [ 4, [ 4, [ 4, [ 4, [ 5, [ 5, [ 5, [ 6, [ 6, [ 8, [ 8, [ 8, [ 8, [ 8, [ 8, [ 8, [ 12, [ 12, [ 12, [ 14, [ 19, [ 20, [ 36, [ 3, [ 3, [ 3, [ 3, [ 3, [ 4, [ 4, [ 4, [ 4, [ 4, [ 4, [ 4, [ 6, [ 6, 6] 6] 8] 8] 8] 8] 12 ] 12 ] 12 ] 20 ] 36 ] 5] 6] 6] 6] 6] 8] 8] 8] 8] 8] 24 ] 24 ] 12 ] 12 ] 12 ] 21 ] 38 ] 20 ] 36 ] 9] 12 ] 15 ] 18 ] 24 ] 5] 6] 6] 7] 12 ] 22 ] 40 ] 6] 6]

Automs 384 384 256 256 256 256 192 192 192 160 144 320 240 240 192 192 128 128 128 128 128 96 96 96 96 96 84 76 80 72 648 432 360 324 288 720 432 432 336 216 176 160 216 216

m

V

Additional relators R 4, S 6, RS &1RS 2R &2S &2R &2S &1 R 4, S 6, ( RS &1 ) 4, [ RS, SR 2S 2 ] R 4, S 8, [ RS &3, SR ] R 4, [ RS, SR ], S 8 R 4, ( RS &3 ) 2, ( RS &1 ) 4, S 8 R 4, ( RS &3 ) 2, S 8, RS 2( R &1S ) 2 R &1S &2 R 4, [ R, S 3 ], ( RS &1 ) 4 R 4, RS &2RS &1R &2S &1, S 12 R 4, ( RS &2 ) 2, S 12 ( RS &1 ) 2, R 4, S 20 R 4, ( RS &1 ) 2, RS 17R &1S &1 R 5, S 5, RS &1R 2S 2R &1SR &1S &1 R 5, ( RS &2 ) 2 R 5, S 6, [ RS, SR ] R 6, S 6, [ RS &2, SR ] ( RS &1 ) 3, R 6, S 6, [ RS, SR ] ( RS &1 ) 2, R 8, S 8 [ R 2, S ], ( RS &3 ) 2, S 8 RS 3R &3S &1 [ RS, SR ], [ RS &1R, S ], R 4S &4 RS &2RS &1R &2S &1, RS 2R &2SR &1S &1 [ R 2, S ], RS 5R &1S &1 [ R 2, S ], [ R, S 3 ], R 2S &6 R 3S &3, ( RS &1 ) 3 R 2S 2R &1S &1, R 6S &6 [ R 2, S ], [ R, S 2 ], R 4S &8 [ R 2, S ], S 3R &4 [ R, S ], S 8R &11 [ R, S ], R 10S &10 [ R, S ], R 9S &9 R 3, S 9, [ RS &2R, S 3 ] R 3, ( S 2R &1 ) 3, S 12 R 3, [ R, S 5 ], ( RS &3 ) 3 R 3, ( S 2R &1 ) 3, [ R, S 6 ] R 3 , [ R, S 4 ] R 4, S 5, ( RS &1 ) 5 R 4, S 6, ( RS &1RS &2 ) 2 R 4, S 6, [ RS &1R, S 2 ] R 4, ( RS &1 ) 3, S 7 R 4, ( RS &1 ) 3, [ R, S 4 ] ( RS &1 ) 2, R 4, S 22 ( RS &1 ) 2, R 4, RS 19R &1S &1 R 6, S 6, [ RS &1R, S ] R 6, S 6, RS &1R 2S &1RS &2

1 1 1 1 2 2 4 3 4 10 36 1 2 1 1 1 4 2 2 2 2 24 24 4 4 6 21 38 20 36 1 1 3 3 6 1 1 1 1 3 11 40 1 1

1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 4 4 2 2 2 4 4 4 4 6 7 19 20 36 1 1 1 1 1 1 1 1 1 1 2 2 1 1


REGULAR MAPS OF SMALL GENUS TABLE I Map R10.15 R10.16 R10.17 R10.18 R10.19 R10.20 R10.21 R10.22 R10.23* R10.24* R11.1 R11.2 R11.3 R11.4 R11.5* R11.6 R11.7 R11.8 R11.9 R11.10 R11.11 R11.12* R11.13* R11.14* R12.1 R12.2 R12.3 R12.4 R12.5 R12.6 R12.7 R12.8* R12.9 R12.10* R12.11* R13.1 R13.2 R13.3 Genus 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 13 13 13 Type [ 6, 6 ] [ 6, [ 6, [ 6, [ 6, [ 9, [ 12 [ 21 [ 22 [ 40 12 ] 12 ] 12 ] 30 ] 18 ] 24 ] 42 ] 22 ] 40 ] 6] 24 ] 24 ] 44 ] 6] 8] 8] 33 ] 16 ] 16 ] 46 ] 24 ] 24 ] 44 ] 15 ] 26 ] 48 ] 14 ] 10 ] 30 ] 28 ] 15 ] 50 ] 26 ] 48 ] Automs 216 144 144 144 120 108 96 84 88 80 480 192 192 176 240 192 192 132 128 128 92 96 96 88 240 208 192 168 160 120 112 120 100 104 96 720 576 288 m
V

235

( Continued ) m
F

Additional relators ) , R 6, S 6, RS &1R 2S &1RS &1R &2S &1 [ R, S 2 ], R 6 ( RS &1 ) 2, R 6, S 12 [ R 2, S ], ( RS &2 ) 2, S 12 [ R 2, S ], ( RS &2 ) 2, RS 8R &1S &2 [ R, S 2 ], [ R 3, S ], SR &2SR &5 [ R 2, S ], R 2S &4 [ R, S ], S 10R &11 [ R, S ], R 10S &12 [ R, S ], R 9S &11 ( RS R 4, S 6, RS &1RS &2RS &1RS &1R &2S &1 R 4, RS &2RS &1R &2S &1, RS 10R &1S &2 ( RS &1 ) 2, R 4, S 24 ( RS &1 ) 2, R 4, RS 21R &1S &1 R 6, S 6, ( R 2S &2 ) 2, RS 3RS &1R &3S &1 ( R 2S &1 ) 2, R 6, ( RS &3 ) 2 R 6, RS &1RS &1R &1SR &1S &1 [ R 2, S ], ( RS &2 ) 2, S &11R &2 ( RS &1 ) 2, R 8, RS 7R &3S &1 [ R 2, S ], ( RS &3 ) 2, RS 6R &1S &2 [ R, S ], S 10R &13 [ R, S ], R 12S &12 [ R 2, S ], [ R, S 2 ], R 6S &6 [ R, S ], R 11S &11 R 4, ( RS &2 ) 2, S 15 ( RS &1 ) 2, R 4, S 26 ( RS &1 ) 2, R 4, RS 23R &1S &1 ( RS &1 ) 2, R 6, S 14 ( RS &1 ) 2, R 8, S 10 [ R 2, S ], [ R, S 3 ], R 4S &6 [ R 2, S ], [ R, S 2 ], R 6S &8 R 2S 2R &1S &1, S 6R &9 [ R, S ], S 12R &13 [ R, S ], R 12S &14 [ R, S ], R 11S &13 R 3, S 10, ( RS &2RS &3 ) 2 R 3, RS 3RS &2R &1SR &1S R 4, [ RS, SR ], ( RS &5 ) 2
&2 2

2 6 6 4 30 9 24 42 22 40 1 12 12 44 1 2 2 33 8 8 46 24 24 44 5 13 48 7 5 30 28 5 50 26 48 1 1 2

1 1 3 3 3 3 6 21 22 40 1 1 2 2 1 2 1 3 4 4 23 24 24 44 1 2 2 3 4 5 7 5 25 26 48 1 1 1

, , , ,

[ 4, [ 4, [ 4, [ 4, [ 6, [ 6, [ 6, [ 6, [ 8, [ 8, [ 23, [ 24, [ 24, [ 44, [ 4, [ 4, [ 4, [ 6, [ 8, [ 10 [ 14 [ 15 [ 25 [ 26 [ 48

, , , , , ,

[ 3, 10 ] [ 3, 12 ] [ 4, 12 ]

&2

,S

12


236

CONDER AND DOBCSANYI TABLE I ( Continued ) m
F

Map R13.4 R13.5 R13.6 R13.7 R13.8 R13.9 R13.10 R13.11 R13.12 R13.13 R13.14 R13.15* R13.16 R13.17 R13.18* R13.19* R13.20 R13.21* R13.22* R14.1 R14.2 R14.3 R14.4 R14.5 R14.6 R14.7 R14.8 R14.9 R14.10 R14.11* R14.12* R15.1 R15.2 R15.3 R15.4 R15.5 R15.6 R15.7 R15.8 R15.9 R15.10 R15.11 R15.12

Genus 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15

Type [ 4, 16 ] [ 4, 16 ] [ 4, [ 4, [ 5, [ 6, [ 6, [ 6, [ 6, [ 6, [ 9, [ 12, [ 12, [ 16, [ 16, [ 16, [ 27, [ 28, [ 52, [ 3, [ 3, [ 3, [ 4, [ 4, [ 6, [ 6, [ 8, [ 10, [ 29, [ 30, [ 56, [ 3, [ 3, [ 3, [ 4, [ 4, [ 4, [ 4, [ 4, [ 6, [ 7, [ 8, [ 8, 28 ] 52 ] 10 ] 6] 12 ] 12 ] 15 ] 39 ] 18 ] 12 ] 12 ] 16 ] 16 ] 16 ] 54 ] 28 ] 52 ] 7] 7] 7] 30 ] 56 ] 16 ] 42 ] 20 ] 35 ] 58 ] 30 ] 56 ] 9] 14 ] 20 ] 6] 18 ] 32 ] 32 ] 60 ] 10 ] 14 ] 12 ] 12 ]

Automs 256 256 224 208 240 288 192 192 180 156 144 144 144 128 128 128 108 112 104 2184 2184 2184 240 224 192 168 160 140 116 120 112 1008 588 480 672 288 256 256 240 240 196 192 192

m

V

Additional relators R 4, RS &2RS &1R &2S &1, S 16 R 4, ( RS &3 ) 2, ( RS &1 ) 4, RS 5R &1S &2R &2S &1 4 R , ( RS &1 ) 2, S 28 R 4, ( RS &1 ) 2, RS 25R &1S &1 R 5, ( R 2S &2 ) 2 ( RS &2 ) 2, R 6, S 6, [ R 2SR &1, SR ] ( RS &2 ) 2, R 6, [ RS, SR ] ( R 2S &1 ) 2, R 6, [ R, S 3 ] [ R 2, S ], ( RS &2 ) 2, S 15 [ R 2, S ], ( RS &2 ) 2, S 13R &2 [ R 3, S ], [ RS, SR ], SR &2SR &5 ( RS &1 ) 2, RS 5R &5S &1 [ R 2, S ], [ R, S 3 ], R 6S &6 [ R 2, S ], R 4S &4 [ RS, SR ], [ RS &1R, S ], RS &1RS [ R 2, S ], [ R, S 2 ], R 8S &8 [ R, S ], S 12R &15 [ R, S ], R 14S &14 [ R, S ], R 13S &13 R 3, S 7, ( RS &2 ) 6 R 3, S 7, ( S 3R &1S 2R &1 ) 3 R 3, S 7, ( S 2R &1 ) 7 R 4, ( RS &1 ) 2, S 30 R 4, ( RS &1 ) 2, RS 27R &1S &1 ( RS &1 ) 2, R 6, S 16 [ R 2, S ], ( RS &2 ) 2, RS 13R &1S ( RS &1 ) 2, R 8, RS 9R &3S &1 [ R 2, S ], S &7R &2 [ R, S ], S 14R &15 [ R, S ], R 14S &16 [ R, S ], R 13S &15

4 4 14 52 2 2 4 4 5 39 6 6 4 8 8 8 54 28 52 1 1 1 15 56 8 42 10 35 58 30 56 1 1 4 1 6 16 16 60 2 7 4 4

1 1 2 2 1 1 1 2 3 3 3 6 6 8 8 8 27 28 52 1 1 1 2 2 3 3 4 5 29 30 56 1 1 1 1 1 1 2 2 2 1 2 2

&5

&1

R 3, S 9, ( RS &2RS &4 ) 2 R 3, ( S 2R &1 ) 3, S 14 R 3, [ R, S 5 ], ( RS &2RS &3 ) 2 R 4, S 6, ( S 2R &1 ) 3 R 4, ( RS &2 ) 2, S 18 R 4, RS &2RS &1R &2S &1, RS 14R &1S &2 R 4, ( RS &1 ) 2, S 32 R 4, ( RS &1 ) 2, RS 29R &1S &1 ( R 2S &1 ) 2, R 6, R 2S 4R &1S &1 [ R, S 2 ], R 7 R 2S 2R &1SR &1S &1 , [ R, S 3 ] ( RS &2 ) 2, ( R 3S &1 ) 2, R 2S &4R &1SR &1S

&1


REGULAR MAPS OF SMALL GENUS TABLE I Map R15.13 R15.14 R15.15 R15.16 R15.17 R15.18* R15.19 R15.20 R15.21* R15.22* R15.23* Genus 15 15 15 15 15 15 15 15 15 15 15 Type [ 8, [ 8, [ 8, [ 8, [ 14 [ 18 [ 22 [ 31 [ 32 [ 32 [ 60 12 ] 12 ] 40 ] 40 ] 35 ] 18 ] 33 ] 62 ] 32 ] 32 ] 60 ] Automs 192 192 160 160 140 144 132 124 128 128 120 m
V

237

( Continued ) m
F

Additional relators ( RS &1 ) 2, R 8, S 12 [ R 2, S ], ( RS &3 ) 2, S 12 [ R 2, S ], ( RS &3 ) 2, RS 7R &1S [ R 2, S ], ( RS &3 ) 2, RS 9R &1S [ R 2, S ], S 5R &2 R 2S 2R &1S &1, R 9S &9 [ R 2, S ], [ R, S 3 ], S 3R &8 [ R, S ], S 14R &17 [ R, S ], R 16S &16 [ R 2, S ], [ R, S 2 ], R 6S &10 [ R, S ], R 15S &15

, , , , , , ,

6 3 40 40 35 6 33 62 32 32 60

4 4 4 4 7 6 11 31 32 32 60

&3 &1

TABLE II Irreflexible ( Chiral ) Rotary Maps of Genus 2 to 15 Map C7.1 C7.2 C8.1 C10.1 C10.2 C10.3* C11.1 C11.2 C11.3 C11.4* C11.5* C11.6* C12.1 C12.2 C14.1 C15.1 Genus 7 7 8 10 10 10 11 11 11 11 11 11 12 12 14 15 Type [ 6, 9 ] [ 7, 7 ] [ 6, 6 ] [ 3, 8 ] [ 4, 8 ] [ 8, 8 ] [ 4, [ 4, [ 4, [ 8, [ 8, [ 12, 8] 8] 12 ] 8] 8] 12 ] Automs 54 56 84 432 144 72 160 160 120 80 80 60 110 110 156 336 m
V

m

F

Additional relators ( RS &2 ) 2, R 6, S 2RS R 7, S 2R &1SR &3 ( RS
&2 2 &1

3 1 2 1 1 1 2 2 3 2 2 3 1 1 2 2

1 1 1 1 1 1 1 1 1 2 2 3 1 1 1 1

R

&3

) , R 6, S 6, R 2S 2RS

&1

R

&3

S

&1

R 3, S 8, S 2R &1S 3R &1SR &1S &3RS R 4, S 8, RS 3( R &1S ) 2 R &1S &1 RSR &1SR &3S &1 R 4, ( RS &3 ) 2, R4, ( RS &3 ) 2, R 4, ( RS &3 ) 2, RS &1RS &2R [ RS &2, SR ], R 2S &1RS &2

&3

R

&1

S 8, RS 2R &1SR &2S &2R &2S &1 S 8, RS &1RS 2R &2S &2R &2S &1 RS 3RS &2R &2S &1 &2 &1 S R 3S 3R &1S &1 , R 4S &4

[ 5, 10 ] [ 5, 10 ] [ 6, 6 ] [ 3, 12 ]

R 5, [ RS &2, SR ] R 5, S 4R &1S &2R &2 ( RS
&2 2

) , R 6 , S 6 , ( R 2S

&1 2

) RS

&1

R

&3

S

&1

R 3, ( RS &5 ) 2, RS 3R &1S 2R

&1

SR

&1

S

&3

R

&1

SR

&1

S

&2


238

CONDER AND DOBCSANYI TABLE III Nonorientable Regular Maps of Genus 3 to 30

Map N4.1 N4.2 N5.1 N5.2 N5.3* N5.4* N6.1 N6.2 N6.3 N7.1 N7.2 N8.1 N9.1 N9.2 N9.3 N10.1 N10.2 N10.3 N10.4 N10.5 N10.6 N11.1 N11.2* N12.1 N12.2 N12.3* N13.1 N13.2 N14.1 N14.2 N14.3

Genus 4 4 5 5 5 5 6 6 6 7 7 8 9 9 9 10 10 10 10 10 10 11 11 12 12 12 13 13 14 14 14

Type [ 4, 6 ] [ 4, 6 ] [ [ [ [ 4, 4, 5, 6, 5 6 5 6 ] ] ] ]

Automs 48 48 120 72 60 36 120 120 160 120 72 504 336 336 60 192 96 96 120 120 120 216 108 240 240 120 120 84 360 120 120

m

V

m

F

Additional relators R 4, TS &1RS &1R &2, S 6 R 4, ( RS &2 ) 2, S 6, S 2RS &1R R 4, S 5, T( S &1R ) R 4, S 6, T( S &1R ) R 5, S 5, ( RS &1 ) 3, ( RS &1 ) 2, R 6, S 6,
3 3

2 2 1 1 1 3 2 2 1 1 3 1 1 1 5 1 4 4 2 2 1 1 1 1 1 1 5 7 1 2 2

1 1 1 1 1 3 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1

&2

T

R &3 R &3, TS &2RS S 2RS &1R &2T S 3R &3T

&3

R

&1

[ 3, 10 ] [ 3, 10 ] [ 4, 5 ] [ 4, 6 ] [ 4, 9 ] [ 3, 7 ] [ 3, 8 ] [ 3, 8 ] [ 6, 10 ] [ 4, [ 4, [ 4, [ 5, [ 5, [ 5, 6] 12 ] 12 ] 6] 6] 6]

R 3, TS &1RS 2R &1S &3R &1 R 3, S &1RS &2RS &2R &1T R 4, S 5, ( RS &1 ) 4, S 2R 2SR &1S R 4, ( RS &1 ) 3, S 6, S 2R 2SR R 4, TS &1RS &1R &2, S 9 R 3, S 7, S
&1 &1

&2

R R

&2

T T

S

&2

&2

( RS

&2 4

)R

&1

T

R 3, S 8, TS &1( RS &2 ) 3 R &1 R 3, S 8, ( RS &2 ) 4, TS &3RS &3RS ( RS &1 ) 2, R 6, S &5R &3T R R R R R R
4 4 4 5 5 5

&4

R

&1

, , , , , ,

S 6, ( RS &1 ) 4, TS &1RS 2R &1S &3R ( RS &2 ) 2, TS 4R &1S &2R &2 TS &1RS &1R &2, S 12 ( RS &2 ) 2, TSR &1SR &2S &2R &2 ( RS &2 ) 2, S &1R 2S &1RS &1R &2T S 6, [ RS, SR ], S &1R 2S &3R &2T

&1

[ 4, 6 ] [ 6, 6 ] [ 4, 6 ] [ 4, 6 ] [ 6, 6 ] [ 4, 15 ] [ 6, 14 ] [ 3, 10 ] [ 5, 10 ] [ 5, 10 ]

R 4, S 6, T ( S &1R ) 3 R &3 R 6, S 6, S 2RS &1R &2T R 4, S 6, S 2R 2SR &1S &2R &2T R 4, S 6, S 3R 2S &3R &2T R 6, S 6, TS &1R 2S &1R &3, TS R 4, TS &1RS &1R &2, S ( RS &1 ) 2, R 6, TR 3S 7 R 3, S 10, S &2RS 3R &1S R 5, TS &3RS &1R &2 R 5, S 2RS &1R &2T
15

&2

RS

&3

R

&1

&4

R

&1

T


REGULAR MAPS OF SMALL GENUS TABLE III Map N15.1 N16.1 N16.2 N16.3 N16.4 N16.5 N16.6 N16.7 N16.8 N17.1 N17.2 N17.3 N17.4* N19.1 N20.1 N20.2 N20.3 N20.4* N20.5* N21.1 N22.1 N22.2 N22.3 N22.4 N23.1 N23.2 N23.3 N25.1 N25.2 N25.3 Genus 15 16 16 16 16 16 16 16 16 17 17 17 17 19 20 20 20 20 20 21 22 22 22 22 23 23 23 25 25 25 Type [ 3, 7 ] [ 3, [ 4, [ 4, [ 4, [ 6, 9] 6] 18 ] 18 ] 10 ] Automs 1092 504 336 144 144 120 120 96 96 720 200 108 100 168 240 240 144 120 120 132 192 192 240 192 1008 336 336 216 156 140 m
V

239

( Continued )
F

m

Additional relators R 3, S 7, S R3 R4 R4 R4 (R , , , ,
&1

1 1 1 6 6 2 2 4 4 1 1 9 5 7 2 2 3 2 2 11 8 8 1 1 1 1 1 9 13 7

1 1 1 1 1 2 2 2 2 1 1 3 5 1 1 1 1 2 2 3 1 1 1 1 1 1 1 1 3 5

( RS

&2 6

)R

&1

T

[ 6, 10 ] [ 8, 12 ] [ 8, 12 ] [ 3, [ 4, [ 6, [ 10, 8] 10 ] 18 ] 10 ]

S 9, TS &1( RS &2 ) 3 R &1 S 6, T( S &1R ) 4 R &3, ( S 2R &1 ) ( RS &2 ) 2, S 7R &1S &2R &2T TS &1RS &1R &2, S 18 2 &1 2 S ) , R 6, R 2S 4R &1S &1, S &1( RS &2 ) 2 R &1T 2 &1 2 ( R S ) , R 6, R 2S 4R &1S &1, TS 2R &1SR &1S &2R &2 &2 2 ( RS ) , S 2RS &1R &2T ( RS &2 ) 2, S &1RS 2R &2T

3

R 3, S 8, TS &1RS 3RS &2R &1SR &1S &3R R 4, [ RS, SR ], S 10, TS &1( RS &3 ) 2 R &2 ( RS &1 ) 2, R 6, TR 3S 9 ( RS &1 ) 2, R 10, S 10, TR 5S &5 R 4, TS
&1

&1

[ 4, 21 ] [ 4, 10 ] [ 4, 10 ] [ 6, 12 ] [ 10, 10 ] [ 10, 10 ] [ 6, 22 ] [ 4, [ 4, [ 6, [ 6, 24 ] 24 ] 6] 8]

RS

&1

R

&2

,S

21

R 4, T ( S &1R ) 3 R &3, ( RS &4 ) 2 R 4, ( RS &4 ) 2, ( RS &1RS &2 ) 2, S &1RS 3R &1S &2R &2T 6 R , S 2RS &1R &2T, ( RS &3 ) 2 ( RS &1 ) 3, S 2RS &1R &2T ( RS &1 ) 3, TS &1RS 2R &3 ( RS R R R R
4 4 6 6 &1 2

) , R 6, TR 3S

11

, , , ,

( RS &2 ) 2, TS 10R &1S TS &1RS &1R &2, S 24 S 6, TS &1R 2S &1R &3 S 2RS &1R &2T, S 8

&2

R

&2

[ 3, 8 ] [ 4, 8 ] [ 4, 8 ] [ 4, 27 ] [ 6, 26 ] [ 10, 14 ]

R 3, S 8, T( S &3R ) 3 S &4R &1 R 4, T( S &1R ) 3 R &3, S 8, S &2RS 3R &1S &4R &1T 4 R , S 8, T( S &1R ) 4 R &3, ( S 2R R 4, TS &1RS &1R &2, S ( RS &1 ) 2, R 6, TR 3S 13 ( RS &1 ) 2, R 10, TR 5S 7
27

&1 3

)


240

CONDER AND DOBCSANYI TABLE III ( Continued )
F

Map N26.1 N26.2 N26.3

Genus 26 26 26

Type [ 3, 10 ] [ 4, 10 ] [ 4, 10 ]

Automs 720 320 320

m

V

m

Additional relators R 3, S 10, ( RS &2 ) 4, TS &1RS 3RS &2R &1SR 4 R , ( RS &1 ) 4, ( RS &4 ) 2, S 10, S 2R 2SR &1S &2R &2T 4 R , ( RS &1 ) 4, ( RS &4 ) 2, S 10, TSR &1S 3R &2S &2R &2 R 4, ( RS &2 ) 2, S 13R &1S &2R R 4, TS &1RS &1R &2, S 30

1 2 2

1 1 1

&1

S

&3

R

&1

N28.1 N28.2 N29.1 N29.2

28 28 29 29

[ 4, 30 ] [ 4, 30 ] [ 3, 12 ] [ 6, 6 ]

240 240 648 324

10 10 1 1

1 1 1 1

&2

T

N29.3 N29.4 N29.5 N29.6 N30.1 N30.2 N30.3 N30.4 N30.5* N30.6 N30.7 N30.8 N30.9 N30.10 N30.11

29 29 29 29 30 30 30 30 30 30 30 30 30 30 30

[ 6, 12 ] [ 6, 12 ] [ 6, 12 ] [ 6, 30 ] [ 4, 6 ] [ 4, 6 ] [ 5, 8 ] [ 5, 8 ] [ 6, 6 ] [ [ [ [ 6, 6, 6, 6, 10 10 10 10 ] ] ] ]

216 216 216 180 672 672 320 320 336 240 240 240 240 240 240

3 3 3 15 1 1 2 2 1 2 2 2 2 2 2

1 1 1 3 1 1 1 1 1 2 2 2 2 1 1

R 3, S 12, RS 4RS &2R &1S 2R &1S &2, S &1( RS &2 ) 4 R &1T R 6, S 6, RS &1R 2SR &1SR &2S &1, RS 3RS &1R &1SR &1S &1, S &2RS &1RS &2R &3T R 6, RS &2RS &1R &2S &1, TS &1RS 2R &1S &3R &1 R 6, TS &1R 2S &1R &3, ( RS &3 ) 2 R 6, [ RS, SR ], ( RS &3 ) 2, TSR &1SRS ( RS &1 ) 2, R 6, S &15R &3T

&2

R

&3

[ 6, 10 ] [ 6, 10 ]

R 4, S 6, S &1RSR &1S 2R &2S &2R &2T R 4, S 6, TS &1RS &1RS &1RS &1R &2, RS 2R 2S 2RS &1R &2S &2R &2S &1 R 5, ( RS &3 ) 2, RS 2( R &1S ) 2 R &1S &2, S 2R 2SR &1S &2R &2T R 5, ( RS &3 ) 2, RS 2( R &1S ) 2 R &1S &2, SR &1S 2R &2S &2R &2T R 6, S 6, ( RS &1 ) 4, TSR &1SR 2S &1R &3, TS &1RS 2R &1S &3R &1 ( R 2S &1 ) 2, R 6, S &1RS &2RS &2R &1T ( R 2S &1 ) 2, R 6, TS 2R &1SR &1S &2R &2 ( R 2S &1 ) 2, R 6, TS &1RS 2R &1S &3R &1 ( R 2S &1 ) 2, R 6, ( RS &4 ) 2, S &2RS 2R &1S &2R &2T 6 R , [ RS, SR ], ( RS &1 ) 4, S &2RS &2R &3T R 6, [ RS, SR ], ( RS &1 ) 4, TS 3RS &2R &3

These relators are essentially representatives of conjugacy classes which generate the corresponding normal subgroup of the appropriate finitelypresented group ( 8 or 8* ), or equivalently, additional relators which produce the full automorphism group of the map when inserted into the given presentation for 8 or 8* as appropriate, but with R, S and T denoting the images of u, v and t respectively. Exactly one map is listed from each class under map isomorphism, duality and reflection.


REGULAR MAPS OF SMALL GENUS

241

4. CONCLUDING REMARKS Several families of maps are identifiable in tables, including the following reflexible orientable maps for each genus n 2: ( a ) Maps of type [ 4n, 4n] with one vertex, 2n edges and one face, and automorphism group D 2n of order 4n; ( b ) Maps of type [ 2n +1, 4n +2 ] with one vertex, 2n + 1 edges and two faces, and automorphism group D 4n +2 of order 8n + 4 ( duals of those in [ 7; Table 8 ] ); ( c ) Maps of type [ 2n +2, 2n +2 ] with two vertices, 2n + 2 edges and two faces, and automorphism group D 2n +2 _C 2 of order 8n + 8 ( see [ 7; Table 8 ] ); ( d ) Maps of type [ 4, 4n] with two vertices, 4n edges and 2n faces, and automorphism group of order 16n ( duals of the Threlfall maps [ 7; Section 8.7 ] ); ( e ) Maps of type [ 4, 2n +2 ] with four vertices, 4n + 4 edges and 2n + 2 faces, and automorphism group of order 16n + 16. Further computations of the sort described above could be carried out to extend the tables, but a large increase in computing time is required to achieve a small increase in the genus range, and so this approach is limited by resources. Nevertheless the approach can also be fruitful in searching for examples of larger genus but of specified type, or to answer questions concerning the action of specific groups on maps or surfaces of low genus. Also, as shown in [ 6 ] ( using a semi-direct product construction to produce infinite families of map automorphism groups ), regular maps exist on non-orientable surfaces of over 77.5 0 of all possible genera. In particular, as noted in [ 6 ] every positive integer g 100 other than 2, 3, 18, 24, 27, 39, 48, 54, 59, 60, 63, 71, 75, 87, 95 and 99 is known to be the genus of some non-orientable regular map. Of the exceptions, non-orientable surfaces of genus 2 or 3 are definitely known not to admit regular maps ( see [ 7 ] ), and the results of our computations confirm unpublished work of Antonio Breda and Steve Wilson showing that also there are no nonorientable regular maps of genus 18, 24 or 27. What of the remaining genera, in this range and beyond? This question is still very much open. ACKNOWLEDGMENTS
The authors are grateful to the N. Z. Marsden Fund and the University of Auckland Research Committee for their support. The authors also acknowledge the use of the MAGMA system [ 3 ] for checking and confirming many of the computations, and are grateful to the referees for suggested improvements to an earlier version of this paper.


242

CONDER AND DOBCSANYI

REFERENCES
1. P. Bergau and D. Garbe, Nonorientable and orientable regular maps, in ``Proceedings of Groups Korea, 1988, '' Springer Lecture Notes in Mathematics, Vol. 1398, pp. 29 42, Springer-Verlag, New YorkáBerlin. 2. N. L. Biggs and A. T. White, ``Permutation Groups and Combinatorial Structures , '' London Math. Society Lecture Note Series, Vol. 33, Cambridge University Press, Cambridge, UK, 1979. 3. W. Bosma and J. Cannon, ``Handbook of Magma Functions,'' University of Sydney, Sydney, 1994. 4. H. R. Brahana, Regular maps and their groups, Amer. J. Math. 49 ( 1927 ), 268 284. 5. M. D. E. Conder and P. Dobcsanyi, Applications and adaptations of the low index subgroups procedure, preprint [ currently available on the world-wide web at the URL http:ááwww.math.auckland.ac.nzátconderápreprintsálowindex.ps ]. 6. M. D. E. Conder and B. J. Everitt, Regular maps on non-orientable surfaces, Geom. Dedicata 56 ( 1995 ), 209 219. 7. H. S. M. Coxeter and W. O. J. Moser, ``Generators and Relations for Discrete Groups, '' 4th ed., Springer-Verlag, Berlin, 1980. 8. P. Dobcsanyi, ``Adaptations, Parallelisation and Applications of the Low-Index Subgroups Algorithm,'' Ph.D. thesis, University of Auckland, 1999. 9. G. A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. London Math. Soc. 37 ( 1978 ), 273 307. 10. S. E. Wilson, Operators over regular maps, Pacific J. Math. 81 ( 1979 ), 559 568.