## Edge-transitive embeddings of complete graphs

Gareth A. Jones School of Mathematics University of Southampton Southampton SO17 1BJ, UK

G.A.Jones@maths.soton.ac.uk

## Abstract

Building on earlier work of Biggs, James, Wilson and the author, and using the Graver-Watkins description of the 14 classes of edgetransitive maps, we complete the classification of the edge-transitive embeddings of complete graphs.

MSC classification: 05C10 (primary); 20B25 (secondary).

Key words: Edge-transitive map, complete graph, Biggs map, James map.

## 1 Introduction

A map on a surface is regular (sometimes called fully regular ) or edgetransitive if its automorphism group acts transitively on vertex-edge-face flags or edges respectively. A map on an orientable surface is orientably regular if its orientation-preserving automorphism group acts transitively on arcs. The regular and orientably regular embeddings of complete graphs are all known, as are their edge-transitive orientable embeddings. Here we complete the classification of their edge-transitive embeddings by determining their non-regular embeddings in non-orientable surfaces.

In 1971 Biggs [1], building on earlier work of Heffter [6], proved:

Theorem 1.1 The complete graph K n has an orientably regular embedding if and only if n is a prime power. /square

The maps Biggs constructed to prove that this condition is sufficient are Cayley maps M n ( c ) for the additive groups of finite fields F n ; in each case the generating set is the multiplicative group F ∗ n = F n \ { 0 } , taken in the cyclic order 1 , c, c 2 , . . . , c n -2 where c is a primitive element of F n (that is, a generator for the cyclic group F ∗ n ).

Example For n = 4 we have F 4 = { 0 1 , , c, c 2 = c -1 = c + 1 , } and the corresponding map M 4 ( c ) is the tetrahedral map on the sphere. The Biggs maps M 5 (2) and M 7 (3) are shown in Figure 1, with opposite sides of the outer square and hexagon identified to form the torus maps { 4 4 , } 1 2 , and { 3 6 , } 1 2 , in the notation of [3, § 8.3 and § 8.4]. Their mirror images are the maps M 5 (3) = ∼ { 4 4 , } 2 1 , and M 7 (5) = ∼ { 3 6 , } 2 1 , .

Figure 1: The Biggs maps M 5 (2) and M 7 (3)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01193v1-figure-9f6ae6e4-a035-4d3b-a215-c6a9b45e35f3.jpg)

In 1985 James and the author [10] proved that the Biggs maps M n ( c ) are the only orientably regular embeddings of complete graphs:

Theorem 1.2 A map M is an orientably regular embedding of K n if and only if M ∼ M = n ( c ) for some primitive element c of F n . Moreover, M n ( c ) and M n ( c ′ ) are isomorphic (as oriented maps) if and only if c and c ′ are equivalent under a field automorphism of F n . /square

↦

It follows that if n = p e for some prime p then there are, up to isomorphism, φ n ( -1) /e orientably regular embeddings of K n , one for each orbit of the Galois group of F n (isomorphic to C e , generated by the Frobenius automorphism t → t p ) on the φ n ( -1) primitive elements of the field. The orientation-preserving automorphism group of M n ( c ) is the affine group

AGL 1 ( F n ); this map is regular if and only if n = 2 3 or 4, in which case the , full automorphism group is isomorphic to V 4 , D 6 or S 4 .

If n ≥ 3 the Petrie dual P ( M n ( c )) of M n ( c ) is a non-orientable edgetransitive embedding of K n , with the same automorphism group as M n ( c ).

In [8] James classified the non-orientable regular embeddings of complete graphs (see also [16] for an independent proof due to Wilson):

Theorem 1.3 The non-orientable regular embeddings of complete graphs K n are the maps { 6 2 , } 3 , { 4 3 , } 3 , { 3 5 , } 5 and { 5 5 , } 3 of characteristic 1 1 1 , , and -3 for n = 3 4 6 , , and 6 . /square

Here the notation { p, q } r , from [3, § 8.6 and Table 8], denotes the largest map of type { p, q } with Petrie length r . The first three of these maps, on the real projective plane, are the antipodal quotients of a hexagon, a cube and an icosahedron on the sphere (see Figure 2, where antipodal boundary points of the discs are identified). The first two are the Petrie duals of the unique regular embeddings M n ( c ) of K 3 and K 4 on the sphere, with the same automorphism groups D 6 and S 4 , while the last two are a Petrie dual pair with automorphism group PSL 2 (5) = ∼ A 5 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01193v1-figure-12ba9f6d-daf6-48de-b833-373c92262874.jpg)

Figure 2: Regular embeddings of K n on the projective plane, n = 3 4 6 , ,

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01193v1-figure-ab7a6cd1-479a-41e7-8e0e-c83bb33c414e.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01193v1-figure-4f093c43-a3d1-4574-86b7-08c6e084922b.jpg)

In [9] James extended Theorem 1.2 to a classification of the orientable edge-transitive embeddings of K n . If 3 &lt; n = p e ≡ 3 mod (4) where p is prime, and c is a primitive element of F n , let M n ( c, j ) be the Cayley map for F n with generating set F ∗ n , where now the cyclic ordering is

$$1, c ^ { j }, c ^ { 2 }, c ^ { j + 2 }, c ^ { 4 }, c ^ { j + 4 }, \dots, c ^ { n - 3 }, c ^ { j + n - 3 }$$

for some odd element j ∈ Z n -1 \ { 1 } . (Taking j = 1 gives the orientably regular Biggs map M n ( c ).)

Theorem 1.4 A map M is an orientable edge-transitive embedding of K n , which is not orientably regular, if and only if M ∼ M = n ( c, j ) for some n , c and j as above. As oriented maps, M n ( c, j ) and M n ( c , j ′ ′ ) are isomorphic if and only if c and c ′ are equivalent under Gal F n and j ′ ≡ j or 2 -j mod ( n -1) . /square

These James maps M n ( c, j ) have automorphism group AHL 1 ( F n ), the unique subgroup of index 2 in AGL 1 ( F n ); their Petrie duals are non-orientable edge-transitive embeddings of K n . The mirror image of M n ( c, j ) is the map M n ( c -1 , 2 -j ) = ∼ M n ( c -1 , j ).

Example The James map M 7 (5 , 5) is shown in Figure 3, taken from [9]. Two of the identifications of sides of the outer 14-gon are indicated by the letters A and B ; the others can be found by C 7 rotational symmetry. The vertices are identified with the elements 0 , 1 , . . . , 6 of F 7 , in clockwise order. There are seven triangular faces and three heptagons. The mirror image M 7 (3 , 3) of this map is given by reflection in the horizontal axis. Each of these maps is a representation of the Fano plane, with the vertices as its points and the triples incident with its triangular faces forming its lines.

Figure 3: An edge-transitive embedding M 7 (5 , 5) of K 7

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01193v1-figure-40cff785-7977-423c-b5a1-3dc347fe6442.jpg)

These two maps M can be drawn as follows on Klein's Riemann surface (or quartic curve) K of genus 3 with automorphism group PSL 2 (7) (see [13],

for instance), so that Aut M ∼ (= C 7 /multicloseright C 3 ) is contained in Aut K . Each of the eight Sylow 7-subgroups S ∼ = C 7 of Aut K preserves three of the 24 faces of the Aut K -invariant tessellation T = { 7 3 , } 8 of K . These three faces are incident with 21 of the 56 vertices of T , and there are 21 more vertices adjacent in T to these. This leaves 14 vertices of T , at graph-theoretic distance 2 from the S -invariant faces, forming two orbits under S . The vertices in each orbit, joined pairwise by geodesics, determine a chiral pair of maps M∼ M = 7 (5 , 5) and M 7 (3 , 3), each invariant under the normaliser Aut M = S /multicloseright C 3 of S in Aut K . Figure 4 shows part of T , with the central face invariant under the group S generated by rotation through 2 π/ 7, and the orbits of S on vertices of T yielding these two maps indicated in black and white. The vertices of each map are the centres of the triangular faces of the other. The three heptagonal faces of each map each contain one of the S -invariant faces of T .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01193v1-figure-5c0b6ce6-fbfe-4cae-a52c-f131ce436ff3.jpg)

B

Figure 4: Vertices of M 7 (5 , 5) and M 7 (3 , 3) on Klein's surface

In order to complete the classification of edge-transitive embeddings of complete graphs, it remains for us to deal with the non-regular non-orientable cases. The main result of this paper is as follows:

Theorem 1.5 A map M is a non-orientable non-regular edge-transitive embedding of a complete graph K n if and only if M is isomorphic to the Petrie dual of a Biggs map M n ( c ) for n ≥ 5 or of a James map M n ( c, j ) for n ≥ 7 .

As an immediate corollary we have the following classification of the edge-transitive embeddings of complete graphs, showing that they are simply the maps listed above:

Theorem 1.6 A map M is an edge-transitive embedding of a complete graph K n if and only if M is isomorphic to a Biggs map M n ( c ) or its Petrie dual, a James map M n ( c, j ) or its Petrie dual, or one of the Petrie dual pair { 3 5 , } 5 and { 5 5 , } 3 of non-orientable regular embeddings of K 6 . /square

A more detailed description of these maps is given in Section 5.

## 2 Algebraic theory of maps

Here we sketch the algebraic theory of maps developed in more detail elsewhere: see [12], for example, and [5] for further background in topological graph theory.

Each map M (possibly non-orientable or with non-empty boundary) determines a permutation representation of the group

$$\Gamma = \left \langle R _ { 0 }, R _ { 1 }, R _ { 2 } \, \right | \, R _ { i } ^ { 2 } = \left ( R _ { 0 } R _ { 2 } \right ) ^ { 2 } = 1 \right \rangle \cong V _ { 4 } * C _ { 2 }$$

/negationslash on the set Φ of flags φ = ( v, e, f ) of M , where v, e and f are a mutually incident vertex, edge and face. For each φ ∈ Φ and each i = 0 1 2, there is , , at most one flag φ ′ = φ with the same j -dimensional components as φ for each j = i (possibly none if φ is a boundary flag). Define r i to be the permutation of Φ transposing each φ with φ ′ if the latter exists, and fixing φ otherwise. (See Figures 5 and 6 for the former and latter cases. In Figure 6 the broken line represents part of the boundary of the map.) Since r 2 i = ( r r 0 2 ) 2 = 1 there is a permutation representation

/negationslash

$$\theta \, \colon \Gamma \to G \, \coloneqq \, \langle r _ { 0 }, r _ { 1 }, r _ { 2 } \rangle \leq \text{Sym} \, \Phi$$

↦

of Γ on Φ, given by R i → r i .

Conversely, any permutation representation of Γ on a set Φ determines a map M in which the vertices, edges and faces are identified with the orbits on Φ of the subgroups 〈 R , R 1 2 〉 ∼ = D ∞ , 〈 R , R 0 2 〉 ∼ = V 4 and 〈 R , R 0 1 〉 ∼ = D ∞ , incident when they have non-empty intersection.

The map M is connected if and only if Γ acts transitively on Φ, as we will always assume. In this case the stabilisers in Γ of flags φ ∈ Φ form a conjugacy class of subgroups M ≤ Γ, called map subgroups .

Figure 5: Generators r i of G acting on a flag φ = ( v, e, f ).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01193v1-figure-c20171a9-f3e2-4dda-8b56-d7c3310ee9ad.jpg)

Figure 6: Flags fixed by r , r 0 1 and r 2 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01193v1-figure-70d9137c-f49c-49b4-bd15-a521cbc94601.jpg)

The map M is finite (has finitely many flags) if and only if M has finite index in Γ, and it has non-empty boundary if and only if M contains a conjugate of some R i , or equivalently some r i has a fixed point in Φ. In particular, M is orientable and with empty boundary if and only if M is contained in the even subgroup Γ + of index 2 in Γ, consisting of the words of even length in the generators R i . We will assume unless stated otherwise that all maps considered have empty boundary.

The automorphism group A = Aut M of M is the centraliser of G in SymΦ. Then A ∼ = N/M where N := N Γ ( M ) is the normaliser of M in Γ. The map M is called regular if A is transitive on Φ, or equivalently G is a regular permutation group, that is, M is normal in Γ; in this case A ∼ = G ∼ = Γ /M , and one can identify Φ with G , so that A and G are the left and right regular representations of G . The map M is edge-transitive if A acts transitively on its edges, or equivalently Γ = NE where E := 〈 R , R 0 2 〉 ∼ = V 4 .

The (classical) dual D ( M ) of M corresponds to the image of M under the automorphism δ of Γ fixing R 1 and transposing R 0 and R 2 . The Petrie dual P ( M ) embeds the same graph as M , but the faces are transposed with Petrie polygons, closed zig-zag paths turning alternately first right and first left at the vertices of M ; this operation corresponds to the automorphism π of Γ transposing R 0 with R R 0 2 and fixing R 1 and R 2 . Both of these operations

D and P preserve automorphism groups and regularity, but D may change the embedded graph, and P may change the underlying surface. The group Ω = 〈 D,P 〉 of map operations generated by D and P , introduced by Wilson in [15], is isomorphic to S 3 , permuting vertices, faces and Petrie polygons; it corresponds to the outer automorphism group Out Γ = Aut ∼ E ∼ = S 3 of Γ acting on maps by permuting conjugacy classes of map subgroups [12].

## 3 Edge-transitive maps

In 1997 Graver and Watkins [4] partitioned the edge-transitive maps M into 14 classes, distinguished by the isomorphism class of the quotient map M / Aut M ; in that year, Wilson [17] gave a similar classification. These classes T correspond to the 14 isomorphism classes of maps N ( T ) with one edge, shown in Figure 7, or equivalently to the 14 conjugacy classes of parent groups , subgroups N = N T ( ) of Γ satisfying Γ = NE (see [11, § 4]). The maps in Figure 7 are all on the closed disc, apart from N (2 P ex), N (5) and N (5 ) on the sphere, ∗ N (4 P ) on the M¨bius band and o N (5 P ) on the real projective plane. The 14 edge-transitive classes include class 1, consisting of the regular maps, and class 2 P ex, consisting of the chiral (non-regular) orientably regular maps. Each map M in class T , with automorphism group A , is a regular covering by A of the basic map N ( T ) for that class; it corresponds to a map subgroup M ≤ Γ with N Γ ( M ) = N T ( ) and N T /M ( ) ∼ = A .

The six rows of Figure 7 correspond to the orbits of Ω on the 14 classes: the duals of the maps in class 2 form class 2 , ∗ while the Petrie duals of the latter form class 2 P ; similar remarks apply to the classes 2 ex , 4 and 5, whereas the classes 1 and 3 are invariant under Ω.

The Reidemeister-Schreier process, applied to the inclusions N T ( ) ≤ Γ, gives the following presentations and free product decompositions:

$$N ( 1 ) = \Gamma = \langle R _ { 0 }, R _ { 1 }, R _ { 2 } \ | \ R _ { i } ^ { 2 } = ( R _ { 0 } R _ { 2 } ) ^ { 2 } = 1 \rangle \cong V _ { 4 } * C _ { 2 },$$

N

$$\text{ gives use following presentations and free group accounts} \colon \\ N ( 1 ) = \Gamma = \langle R _ { 0 }, R _ { 1 }, R _ { 2 } \, | \, R _ { i } ^ { 2 } = ( R _ { 0 } R _ { 2 } ) ^ { 2 } = 1 \rangle \cong V _ { 4 } \ast C _ { 2 }, \\ N ( 2 ) = \langle S _ { 1 } = R _ { 1 }, S _ { 2 } = R _ { 1 } ^ { R _ { 0 } }, S _ { 3 } = R _ { 2 } \, | \, S _ { 1 } ^ { 2 } = S _ { 2 } ^ { 2 } = S _ { 3 } ^ { 2 } = 1 \rangle \cong C _ { 2 } \ast C _ { 2 } \ast C _ { 2 }, \\ N ( 2 \exp ) = \langle S _ { 1 } = R _ { 2 }, S = R _ { 0 } R _ { 1 } \, | \, S _ { 1 } ^ { 2 } = 1 \rangle \cong C _ { 2 } \ast C _ { \infty }, \\ N ( 3 ) = \langle S _ { 0 } = R _ { 1 }, \, S _ { 1 } = R _ { 1 } ^ { R _ { 0 } }, \, S _ { 2 } = R _ { 1 } ^ { R _ { 2 } }, \, S _ { 3 } = R _ { 1 } ^ { R _ { 0 } R _ { 2 } } \, | \, S _ { i } ^ { 2 } = 1 \rangle \cong C _ { 2 } \ast C _ { 2 } \ast C _ { 2 }, \\ N ( 4 ) = \langle S _ { 1 } = R _ { 1 }, S _ { 2 } = R _ { 1 } ^ { R _ { 2 } }, \, S = ( R _ { 1 } R _ { 2 } ) ^ { R _ { 0 } } \, | \, S _ { 1 } ^ { 2 } = S _ { 2 } ^ { 2 } = 1 \rangle \cong C _ { 2 } \ast C _ { 2 } \ast C _ { \infty }, \\ N ( 5 ) = \langle S = R _ { 1 } R _ { 2 }, S ^ { \prime } = S ^ { R _ { 0 } } \, | \, - \rangle \cong C _ { \infty } \ast C _ { \infty } \cong F _ { 2 }.$$

Figure 7: The basic maps N ( T ) for the 14 edge-transitive classes T

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01193v1-figure-baa6298b-6098-4cb9-825c-69d6df2f0347.jpg)

(Here F 2 denotes a free group of rank 2.) Applying elements of Aut E ∼ = Ω, permuting R , R 0 2 and R R 0 2 , gives presentations for the other (isomorphic) parent groups in each orbit of Ω.

## 4 Proof of Theorem 1.5

It is easy to see that P ( M n ( c )) and P ( M n ( c, j )) have the stated properties.

/negationslash

/negationslash

Conversely, if M is a non-regular non-orientable edge-transitive embedding of K n , then it is in one of the 10 edge-transitive classes T = 1, 2 P ex, 5 or 5 , since the maps in class 1 are regular, while those in the other three classes ∗ are orientable. The cases n ≤ 3 are easily dealt with, so assume that n ≥ 4. If T = 2 ex or 5 ∗ P then M = P ( M ′ ) for some edge-transitive embedding M ′ of K n in class 2 P ex or 5 ; ∗ as such, M ′ is orientable, so it is isomorphic to a map M n ( c ) or M n ( c, j ) classified in Theorem 1.2 or 1.4, as required. We may therefore assume that T = 2 ex or 5 ∗ P . This leaves only T = 2, 2 , 2 ∗ P , 2 ex, 3, 4, 4 ∗ and 4 P , so it is sufficient to eliminate these cases.

The edges of K n may be identified with the distinct pairs of vertices, so edge-transitivity implies that the group A = Aut M permutes these pairs transitively, that is, it acts 2-homogenously on the vertices. It permutes the vertices faithfully since n ≥ 4, and transitively since K n is not bipartite; the latter property rules out classes T = 2, 3 and 4, since the corresponding maps N ( T ) have two vertices, so only the classes T = 2 , 2 ∗ P , 2 ex, 4 ∗ and 4 P remain. If A has odd order then, as a quotient of the group N T ( ) with a free product decomposition given above, it must be cyclic; however, a cyclic group cannot be 2-homogenous of degree n ≥ 4, so A has even order. It thus has an element transposing two vertices, so it is 2-transitive on the vertices.

Each edge of M is therefore reversed by some automorphism (a reflection or half turn), so the single edge of N ( T ) must be free, ruling out the classes T = 2ex, 4 ∗ and 4 P . Only the classes 2 ∗ and 2 P remain, with A sharply 2-transitive on the vertices (since M is not regular), and the stabiliser of an edge generated by a reflection or a half-turn respectively, transposing its two incident vertices. Zassenhaus [18] showed that any sharply 2-transitive finite group can be identified with AGL 1 ( F ) acting naturally on a near-field F . Since M is a map, the stabiliser A 0 of the vertex 0 must be a cyclic or dihedral group of order n -1, acting regularly on the set F \{ } 0 of neighbours of 0. Now A acts on the vertices as a Frobenius group F /multicloseright A 0 , so A 0 is a Frobenius complement; these contain at most one involution (see [7, Satz V.18.1(a)] or [14, Theorem 18.1(iii)]), so they cannot be dihedral, and hence A 0 is cyclic. Since T = 2 ∗ or 2 P , N T ( ) is generated by involutions, and hence so are its epimorphic images A and A 0 , giving n -1 ≤ 2, a contradiction. /square

## 5 Summary of properties of the maps

The following basic properties of the maps classified in Theorem 1.6 are taken from [1, 8, 9, 10] or have been demonstrated earlier in this paper.

For each prime power n = p e there are φ n ( -1) /e Biggs maps M n ( c ), all orientable. The mirror image of M n ( c ) is M n ( c -1 ). For each n = 2 3 4 the , , unique map M n ( c ) is regular (in class 1), of type { 2 1 , } 2 , { 3 2 , } 6 or { 3 3 , } 4 and genus 0, with automorphism group V 4 , D 6 or S 4 . For n ≥ 5 these maps are orientably regular (in class 2 P ex) with automorphism group AGL 1 ( F n ); they have type { m,n - } 1 2 p where m = ( n -1) / 2 or n -1 as n ≡ 3 mod (4) or not, and have genus ( n 2 -7 n +4) 4 or ( / n -1)( n -4) / 4 respectively.

The maps P ( M n ( c )) for n ≥ 3 are non-orientable, with the same automorphism group as M n ( c ); they are in class 1 or 2 ex as ∗ n ≤ 4 or n ≥ 5. They have type { 2 p, n - } 1 m where m is as above, and characteristic

$$\chi = n \left ( 1 - \frac { n - 1 } { 2 } + \frac { n - 1 } { 2 p } \right ).$$

↦

/negationslash

If 3 &lt; n = p e ≡ 3 mod (4), there are ( n -3) φ n ( -1) / 4 e James maps M n ( c, j ), all orientable, with mirror image M n ( c -1 , 2 -j ). They are in class 5 , ∗ with automorphism group AHL 1 ( F n ) consisting of the transformations v → av + b in AGL 1 ( F n ) such that a is a non-zero square in F n . This group has two orbits on the faces: if j, 2 -j ≡ ( n -1) / 2 mod ( n -1) they have cardinality n n ( -1 , j ) and n n ( -1 2 , -j ) and the genus is n 4 (( n -3) -2( n -1 , j ) -2( n -1 2 , -j )) + 1, whereas if j or 2 -j ≡ ( n -1) / 2 mod ( n -1) they have cardinality n and n n ( -1) / 2 p and the genus is ( n -1)( n p ( -1) -4 p / ) 4 p . There is a single orbit of n n ( -1) /l Petrie polygons, each polygon having length l = 2( n -1) / n ( -1 2( , j -1)).

The maps P ( M n ( c, j )) are non-orientable, with automorphism group AHL 1 ( F n ); they are in class 5 P , and have type { l, n - } 1 and characteristic

$$\chi = n \left ( 1 - \frac { n - 1 } { 2 } + \frac { n - 1 } { l } \right ).$$

For n = 6 the Petrie dual pair { 3 5 , } 5 and { 5 5 , } 3 are non-orientable, with χ = 1 and -3; they are regular, with automorphism group PSL 2 (5) = ∼ A 5 .

These maps M are all vertex-transitive. Indeed, in all cases Aut M has a subgroup acting regularly on the vertices: when n is a prime power there is a unique such subgroup, namely the additive group of F n acting by

translations, whereas when n = 6 there is a conjugacy classes of ten such subgroups, isomorphic to S 3 . Apart from the James maps M n ( c, j ), these maps are all face-transitive. They are all arc-transitive with the exception of the James maps and their Petrie duals.

## 6 Edge-transitive embeddings with boundary

As an addendum we show in Figure 8 those edge-transitive maps which embed complete graphs K n in surfaces with non-empty boundary. (A general theory of maps with boundary was developed by Bryant and Singerman in [2].)

Figure 8: Edge-transitive embeddings of K n with boundary, n = 2 3 ,

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01193v1-figure-96c7f2e6-a53b-4ba3-86d8-2f351f876973.jpg)

There are three maps each for n = 2 and 3, and none for n ≥ 4. (This follows easily from a wider study of edge-transitive maps with boundary in [11, § 17].) The first five shown here are on the closed disc, while the last is on the M¨bius band. The first two embeddings of o K 2 are in class 1, while the third is in class 2; their automorphism groups are isomorphic to V 4 , C 2 and C 2 . The three embeddings of K 3 , all with automorphism group S 3 , are in classes 1, 2 ∗ and 2 P respectively.

## References

- [1] N. L. Biggs, Classification of complete maps on orientable surfaces, Rend. Math. (6) 4 (1971), 645-655.

| [2]   | R. P. Bryant and D. Singerman, Foundations of the theory of maps on surfaces with boundary, Quart. J. Math. Oxford Ser. (2) 36 (1985), 17-41.       |
|-------|-----------------------------------------------------------------------------------------------------------------------------------------------------|
| [3]   | H. S. M. Coxeter and W. O. J. Moser, Generators and Relations for Discrete Groups , 4th ed., Springer-Verlag, Berlin - Heidelberg - New York, 1980. |
| [4]   | J. E. Graver and M. E. Watkins, Locally finite, planar, edge-transitive graphs, Mem. Amer. Math. Soc. 126 (1997), no. 601.                          |
| [5]   | J. L. Gross and T. W. Tucker, Topological Graph Theory , Wiley, New York (1987).                                                                    |
| [6]   | L. Heffter, ¨ Uber metazyklische Gruppen und Nachbarconfigurationen, Math. Ann. 50 (1898), 261-268.                                                 |
| [7]   | B. Huppert, Endliche Gruppen I , Springer-Verlag, Berlin - Heidelberg - New York, 1979.                                                             |
| [8]   | L. D. James, Imbeddings of the complete graph, Ars Combin. 16 (1983), B, 57-72                                                                      |
| [9]   | L. D. James, Edge-symmetric orientable imbeddings of complete graphs, European J. Combin. 11 (1990), 133-144.                                       |
| [10]  | L. D. James and G. A. Jones, Regular orientable imbeddings of com- plete graphs, J. Combin. Theory Ser. B 39 (1985), 353-367.                       |
| [11]  | G. A. Jones, Automorphism groups of edge-transitive maps, arXiv:1605.09461v3 [math.CO].                                                             |
| [12]  | G. A. Jones and J. S. Thornton, Operations on maps, and outer au- tomorphisms, J. Combin. Theory Ser. B 35 (1983), 93-103.                          |
| [13]  | S. Levy (ed.), The Eightfold Way: the Beauty of Klein's Quartic Curve , MSRI Publications, Berkeley, 2001.                                          |
| [14]  | D. S. Passman, Permutation Groups , W. A. Benjamin, New York - Amsterdam, 1968.                                                                     |

- [15] S. E. Wilson, Operators over regular maps, Pacific J. Math. 81 (1979), 559-568.
- [16] S. E. Wilson, Cantankerous maps and rotary embeddings of K n , J. Combinatorial Theory Ser. B 47 (1989), 262-273.
- [17] S. E. Wilson, Edge-transitive maps and non-orientable surfaces, Math. Slovaca 47 (1997), 65-83.
- [18] H. Zassenhaus, Kennzeichnung endlicher linearer Gruppen als Permutationsgruppen, Abh. Math. Sem. Hamburg 11 (1936), 17-40.
Gareth A. Jones
Edge-transitive embeddings of complete graphs
Building on earlier work of Biggs, James, Wilson and the author, and using
the Graver-Watkins description of the 14 classes of edge-transitive maps, we
complete the classification of the edge-transitive embeddings of complete
graphs.