Two Notes on Maps and Surface Symmetry

Abstract

The first note of this paper determines for which g the orientable surface of genus g can be embedded in euclidean 3-space so as to have prismatic, cubical/octahedral, tetrahedral, or icosahedral/dodecahedral symmetry. The second note proves, through entirely elementary methods, that the clique number of the graph underlying a regular map is m = 2, 3, 4, 6; for m = 6 the map must be non-orientable and for m = 4, 6 the graph has a K _m factorization. Here a regular map is one having maximal symmetry: reflections in all edges and full rotational symmetry about every vertex, edge and face.

In this note, we prove two unrelated results about maps and surface symmetry.

The first concerns the possible finite symmetry, under euclidean isometry, of a surface of genus g embedded in 3-space. The theorem was inspired by a question from Bojan Mohar asking why the sculpture “The group of genus two” by DeWitt Godfrey [5], which appears on the cover of the journal Ars Combinatorica Mathematica, shows almost none of the rotational symmetry of the map.

Any finite group A of euclidean isometries of 3-space fixes the barycenter O of an orbit of A and hence leaves invariant the unit sphere centered at O. Thus the possibilities for A are just the symmetry groups of the n-prism, the Platonic solids (cube/octahedron, tetrahedron, and icosahedron/dodecahedron), and their subgroups. For each of these four types of symmetry, we show that for all but finitely many g, the surface of genus g can be embedded so as to have the given symmetry type, and we give the finite list of excluded g. Given a finite set X of natural numbers, let L(X) be the set of all linear combinations of elements of X with nonnegative integral coefficients. Note that if gcd(X) = 1, then L(X) contains all sufficiently large integers, by the “postage stamp” problem.

FormalPara Theorem A (Surface Symmetry in 3-Space).

Let S be a surface of genus g. Then S can be embedded in 3-space so as to have the symmetry of:

• The n-prism if and only if g ≡ 1 (mod n) or g ∈ L(n,n − 1);

• The cube or octahedron if and only if g ∈ L(16,18,12) + k, where k = 0,5,7,11,13;

• The tetrahedron if and only if g ∈ L(8,6) + k, where k = 0,3,5,7;

• The isosahedron or dodecahedron if and only if g ∈ L(40,48,30) + k where k = 0,11,19,29,31.

Moreover, S can be embedded with n-prism symmetry if and only if it can be embedded with n-fold rotational symmetry. Similarly, S can be embedded with full cubical (respectively, tetrahedral, icosahedral) symmetry if and only if it can be embedded with orientation-preserving cubical (respectively, tetrahedral, icosahedral) symmetry.

The second result concerns the clique number of a regular map. A map M is an embedding of a finite graph G in a closed surface S such that the interior of each face (component of S − G) is homeomorphic to an open disk; we call G the underlying graph of the map and S the underlying surface. An automorphism of the map is an automorphism of the graph that can be extended to a homeomorphism of the surface (combinatorially, the automorphism must take any cycle in G bounding a face to another such cycle). The collection of all such automorphisms forms a group, denoted Aut(M). A map M is regular if Aut(M) acts transitively on vertex-edge-face incidence triples (usually call flags). Intuitively, a regular map generalizes the Platonic solids in having full rotational symmetry about each vertex and face, as well as reflective symmetry. In particular, the stabilizer of any vertex acts on its d neighbors as the dihedral group D _d acting on the vertices of a regular d-sided polygon; we call such an action of D _d naturally dihedral. The study of regular maps goes back to the 1920s and Coxeter and Moser [4] has a whole chapter on them. The survey article [11] covers most of the history of regular maps, including recent advances like [3].

Note that our use of “regular” in the case of orientable maps, is sometimes called reflexibly regular. By contrast, a map M on an orientable surface that has full rotational symmetry about each vertex and face center, but not necessarily any orientation-reversing symmetry, is called orientably regular, and if there is no orientation-reversing symmetry, it is called chiral.

The clique number of a graph G is the largest m such that the complete graph K _m is a subgraph of G. We say that G has an H-factorization if there is a collection of edge-induced subgraphs G _i , all isomorphic to H, such that every edge is an exactly one G _i .

FormalPara Theorem B (Cliques in Regular Maps).

The clique number of the graph G underlying a regular (reflexible) map M is m = 2,3,4 or 6. Moreover, if m = 6, then M must be non-orientable and for m = 4,6 the graph G has a K _m -factorization.

We also give the following purely graph-theoretic version:

FormalPara Theorem C (Cliques in Graphs with Dihedral Vertex Stabilizers).

Let G be a graph with A ⊂ Aut(G) such that for each vertex v, the action of the vertex stabilizer A _v on edges incident to v is naturally dihedral. Then the clique number of G is m = 2,3,4,6. If m ≥ 3, the action of A is vertex-transitive and if m = 4,6, then G has a K _m -factorization.

The proofs for the clique results are astonishingly simple and depend on the measure of an angle, which appears to be a new concept for maps. Corollaries of Theorem B are classical theorems on the possible complete graphs underlying regular orientable and non-orientable maps, obtained using entirely algebraic methods, especially Frobenius groups.

1 Surface Symmetry in 3-Space

Our proof of Theorem A is by cases. We first recall some facts from [6] about a finite group acting A on a closed orientable surface S by orientation-preserving homeomorphisms. If x ∈ S, let A _x be the stabilizer of x in A. Then x has a neighborhood N _x that is equivariant under A, that is if a ∈ A _x , then a(N _x ) = N _x and otherwise N _x and a(N _x ) are disjoint. Moreover, A _x is cyclic with a generator a _x that on N _x looks like the map z → z ^r in the complex plane, where r =  | A _x  | .

Associated with the action of A on S is the quotient map p: S → S∕A, where S∕A is the surface obtained by identifying each orbit under A to a single point. Note that S∕A is a surface since p(N _x ) is a disk about p(x). Let X = { x ∈ S:  | A _x  |  > 1} and let Y = p(X). Then p is a local homeomorphism except at x ∈ X, making p a (regular) branched covering with branch set Y = p(X). For each y ∈ Y, the common number r _y  =  | A _x  | for any x ∈ p ⁻¹(y) is called the order of the branch point y. If S has genus g and S∕A has genus h, then Euler’s formula $2g - 2 = E - V - F$ gives us the Riemann-Hurwitz equation:

$$\displaystyle{2g - 2 = \vert A\vert \left ((2h - 2) +\varSigma _{y\in Y }\left (1 - \frac{1} {r_{y}}\right )\right ),}$$

For later use, we observe that if h = 0, then a generating set for A is obtained by choosing, for each y ∈ Y, one x ∈ p ⁻¹(y) and a generator for A _x .

Prismatic symmetry. We first consider a surface S with n-fold rotational symmetry about an axis in 3-space. Since the axis intersects S in an even number of points, the number of branch points is even and each has order n − 1. Thus:

$$\displaystyle{2g - 2 = n\left ((2h - 2) + 2b\frac{n - 1} {n} \right )\text{ so }g = 1 + (h - 1)n + b(n - 1).}$$

If b = 0, then g ≡ 1 (mod n). Otherwise,

$$\displaystyle{g = 1 + (h - 1)n - 1 + (b - 1)(n - 1) + (n - 1) = hn + (b - 1)(n - 1)}$$

so in this case g ∈ L(n, n − 1).

To show these conditions on g are sufficient, we construct for each case a model of surface S in 3-space having the required symmetry. For g ≡ 1 (mod n), we take the standard torus in 3-space and attach n surfaces of genus h along n disks invariant under the rotation. For $g = hn + (b - 1)n$, where b > 0, we begin with a surface P _n in 3-space obtained from the boundary of a thickening of a dipole consisting of two vertices with n edges connecting the vertices, so that the dipole is invariant under an n-fold rotation about the axis through the two vertices. The genus of P _n is n − 1. We can then string together b − 1, copies of P _n to obtain a surface of genus $(b - 1)(n - 1)$ having n-fold rotational symmetry about a central axis with 2b branch points of order n (for $b - 1 = 0$, we have simply a sphere with branch points of order n at the north and south poles). Then we can add n surfaces of genus h at n disks symmetrically placed either on the midpoints of edges of the central dipole (if b − 1 is odd) or around a neck dividing the surface in half (if b − 1 is even). The result is a surface of genus $g = hn + (b - 1)n$ with the required symmetry.

We observe that the models we have constructed also have antipodal and reflective symmetry on n planes passing through the axis of rotation. Thus these models have full n-prism symmetry. Conversely, if any surface has n-prism symmetry, it also must also have n-fold rotational symmetry, and hence must satisfy g ≡ 1 (mod n) or $g = hn + (b - 1)n$ for b > 0.

Cubical symmetry. We first assume that the surface S embedded in 3-space is invariant under the orientation-preserving automorphism group A of a cube centered at the origin O; it is well known that A is isomorphic to the full symmetric group S ₄. The cube has four axes of 3-fold rotational symmetry, three of 4-fold rotational symmetry, and six of 2-fold symmetry. Each axis passes through O and pierces the surface S in the same number of points in each half. If O is inside the solid bounded by S, this number must be odd; if O is outside the solid, then this number is even. Thus, if O is inside S, we have:

$$\displaystyle{2g - 2 = 24\left (2h - 2 + (2b + 1)\frac{2} {3} + (2c + 1)\frac{3} {4} + (2d + 1)\frac{1} {2}\right )}$$

Simplifying, we get $g = 16b + 18c + 12(2h + d)$ so g ∈ L(16, 18, 12).

If O is outside S, then

$$\displaystyle{2g - 2 = 24\left ((2h - 2) + 2b\frac{2} {3} + 2c\frac{3} {4} + 2d\frac{1} {2}\right )}$$

Simplifying, we get $g = -23 + 16b + 18c + 12(2h + d).$ In this second case, if at least two of the coefficients of b, c, (2h + d) is nonzero, then it is easily checked that g ∈ L(16, 18, 12) + k, where k = 5, 7, 11. If h = 0, it is impossible for only one of b, c, d to be nonzero, since otherwise A is generated by A _x with all x on the same axis, making A cyclic. Thus we can assume that h > 0. The only cases for g ∉ L(16, 18, 12) + k, for k = 5, 7, 11 are g = 1 for (h, d) = (1, 0) and g = 13 for (h, d) = (1, 1). But the only groups acting without fixed points on the torus are abelian [6] so g = 1 is impossible.

We conclude that for orientation-preserving cubical symmetry, we need g ∈ L(16, 18, 12) + k, where k = 0, 5, 7, 11, 13. Now we build a model surface S for all these cases, based on the branch point information in the coefficients b, c, d, h. We begin with a cube centered at O and consider first the cases where O is inside the surface S. We attach to each vertex a string of 2b thickened dipoles P ₃, to the center of each face a string of 2c thickened dipoles P ₄, to the midpoint of each edge a string of 2d thickened dipoles P ₂, and to each point in the orbit of a nonbranch point a string of h thickened dipoles P ₂. The boundary of the resulting solid has genus

$$\displaystyle{2b(8) + 3c(6) + (2h + d)12 = 16b + 18c + 12(2h + d).}$$

If we take the resulting solid and drill a hole between antipodal vertices through the center O, we add $8 - 1 = 7$ to the genus. Holes between antipodal face-centers adds $6 - 1 = 5$ and holes between antipodal edge-midpoints, adds $12 - 1 = 11$. If we drill holes between both vertices and face-centers, we add $8 + 6 - 1 = 13$ to the genus. Thus we get all:

$$\displaystyle{g \in L(16,18,12) + k\text{ where }k = 0,5,7,11,13.}$$

Tetrahedral symmetry. Again, we start with a tetrahedron centered at O and consider only orientation-preserving symmetries; the group in this case is the alternating group A ₄. There are four axes of 3-fold symmetry between each vertex and the center of the opposing face and three axes between midpoints of opposite edges. If O is inside the surface, there are an odd number 2b ^′ + 1 and 2b ^{′ ′} + 1 of intersection points on each half of a vertex-face axis and 2c + 1 on each edge-edge axis. Thus if $b = b^{{\prime}} + b^{{\prime\prime}} + 1$, we have:

$$\displaystyle{2g - 2 = 12\left (2h - 2 + 2b\frac{2} {3} + (2c + 1)\frac{1} {2}\right )\text{ so }g = 8b + 6(2h + c) - 8.}$$

Since b ≥ 1, we have g ∈ L(8, 6). If instead C is outside the surface, we get:

$$\displaystyle{2g - 2 = 12\left (2h - 2 + 2b\frac{2} {3} + 2c\frac{1} {2}\right )\text{ so }g = 8b + 6(2h + c) - 11.}$$

Then g = 1 for $h = 1,b = 0,c = 0$ or $b = 0,h = 0,c = 2$. The first is again impossible since any group acting without fixed points on the torus is abelian. The second is impossible since then the group action would be generated by rotations around only one axis. In all other cases, g ∈ L(8, 6) + k for k = 3, 5, 7. 

For the models, we start with the tetrahedron and attach a string of b dipoles P ₃ at each of the four vertices and a string of c dipoles P ₂ at the midpoint of each edge to make a surface of genus $g = 8b + 6c$ with orientation-preserving tetrahedral symmetry. Drilling holes from each vertex to the center or each edge midpoint to the center or both, gives, as desired, all;

$$\displaystyle{g \in L(8,6) + k\text{ where }k = 0,3,5,7.}$$

Icosahedral symmetry. We start again with an icosahedron centered at O and consider only orientation-preserving symmetries; the group in this case is A ₅. From the Riemann-Hurwitz equation, the situation is exactly the same as for the cube, only with branch points of order 3, 5 and 2. If the center is inside the surface, we get $g = 40b + 48c + 30(2h + d)$. If the center is outside the surface, we get

$$\displaystyle{g = 40b + 48c + 30(2h + d) - 59.}$$

In this case, as long as at least two of b, c, 2h + d is nonzero, then g ∈ L(40, 48, 30) + k, where k = 11, 19, 29. As with the cube, if h = 0, it is impossible for only one of b, c, d to be nonzero. Then the only remaining case is g = 1 for (h, d) = (1, 0) and g = 31 for (h, d) = (1, 1). Again, g = 1 is impossible since A ₅ is not abelian, so we have g ∈ L(40, 48, 30) + k, where k = 11, 19, 29, 31.

For models, we attach b dipoles P ₃ at vertices, c dipoles P ₅ at face centers, and c dipoles P ₂ at edge midpoints. We can also drill 6 tunnels between antipodal vertices, 10 between antipodal face centers, and 15 between antipodal edge midpoints, or any combination, giving all

$$\displaystyle{g \in L(40,48,30) + k,\mbox{ where }k = 0,11,19,29,31.}$$

For the cube, tetrahedron, and icosahedron, our models all can be constructed to have reflective symmetry, so our conditions on g guarantee not only orientation-preserving symmetry of the desired type, but also the full symmetry. Conversely, any surface of genus g having full symmetry automatically has orientation-preserving symmetry so g must satisfy our conditions. □ 

For the cube and tetrahedron, the given formulas for g lead to a list of excluded g. For the cube, it is g = 1, 2, 3, 4, 6, 8, 9, 10, 14, 15, 20, 22, 26, 38. For the tetrahedron, the excluded list is g = 1, 4, 10. For the icosahedron, the list is long, but finite.

For prismatic symmetry, we have $g \equiv 1\pmod n$ or b > 0 and

$$\displaystyle{g = hn + (b - 1)(n - 1)n = qn - r\text{ where }q = h + b - 1 \geq r = b - 1}$$

Notice if r > n, we can write instead $g = (q - 1)n - (r - n)$ with $q - 1 \geq (n - r)$ so we can assume r ≤ n. If we fix n, the pattern for the genera g allowing n-fold rotational symmetry is clear. For example, when n = 6, we first have all g ≡ 0, 1 (mod 6). The we slowly fill in the remaining residues classes as g increases. In the following sequence we have put the missing g in parenthesis:

$$\displaystyle{g = 0,1,(2 - 4)5,6,7(8 - 9),10,11,12,13,(14),15,16,\cdots }$$

Since we can always handle $r = n - 1$ using g ≡ 1 (mod n), the largest r we have to worry about is $r = n - 2$. Thus we have:

Corollary 1.

Given n > 1, all surfaces of genus $g > (n - 3)n - (n - 2) = (n - 2)^{2} - 2$ can be embedded with n-fold rotational symmetry in 3-space.

In general, given a group A, we can ask for the genera g such that A acts, preserving orientation, on the surface of genus g, where now we do not require the action come from an embedding in 3-space. Kulkarni’s Theorem [8] shows that there is a number n(A) such that if A acts on the surface of genus g preserving orientation, then g ≡ 1 (mod n(A)) and that there is an action for all but finitely many such g. The number n(A) follows from the Riemann-Hurwitz equation and is easily computed from the exponent of the Sylow p-subgroups of A, with an extra technical condition for p = 2. In particular, a group A acts on almost all surfaces if and only if it is almost Sylow cyclic and does not contain Z ₂ × Z ₄ [12]; the group A is almost Sylow cyclic if its Sylow p-subgroup A _p is cyclic when p is odd and has a cyclic group of index two, when p = 2. On the other hand, for any A, determining the finite exceptions is almost impossible, even for the case of the cyclic group of order n, when n is highly composite (see for example, [10]).

In addition to changing the group A, we can also consider immersed surfaces, which would allow non-orientable surfaces in 3-space. That problem is considered in [9]. The situation for bordered surfaces is considered by Cavendish and Conway [2].

2 The Clique Number of a Regular Map

Let M be a map. If u and w are vertices adjacent to v, we call uvw an angle at v. A local orientation of the map at a vertex v of valence d defines a cyclic order $u_{1},u_{2},\cdots u_{d}$ to the vertices adjacent to v We define the measure of angle u _i vu _j , denoted m(u _i vu _j ), as the smaller of | i − j | and $d -\vert i - j\vert$; in particular, m(u _i vu _j ) ≤ d∕2. Map automorphisms preserve angle measure, since they preserve or reverse local orientations. If M is regular, because of the dihedral action of the stabilizer of v, given any angle uvw, there is an automorphism fixing v and interchanging u and w. It follows that if uvw is a triangle (3-cycle) in G, then all its angles have the same measure.

Theorem B.

Let M be a regular map whose underlying graph G has no multiple edges. Then the clique number of G is m = 2,3,4,6. In the case m = 4, any 4-clique H is invariant under a 3-fold rotation about any vertex in H and under a reflection in any edge of H; in particular, the valence d of G is divisible by 3. For m = 6, a 6-clique H is invariant under a 5-fold rotation about any vertex of H and under a reflection in any edge of H; in particular, d is divisible by 5. Moreover, for m = 6, the map must be non-orientable. For both m = 4 and m = 6, the graph G has a K _m -factorization.

Proof.

Suppose that G has a K ₄ subgraph H with vertices u, v, w, x with u, v, w consecutive around x. Let $m(uxv) = a,m(vxw) = b$, and m(uxw) = c. Without loss of generality, we can assume that a ≤ b ≤ c. There are two possibilities: either a + b > c, in which case $a + b + c = d$, or $a + b = c$.

Suppose first that $a + b + c = d$. There are four triangles in H. One has all angles a, one b and one c. The fourth triangle has angles $d - (a + b),d - (b + c)$ and $d - (c + a)$. Thus

$$\displaystyle{d - (a + b) = d - (b + c) = d - (c + a).}$$

Since $a + b + c = d$, we have $a = b = c = d/3$. Note that in this case, H is invariant under 3-fold rotation about x and reflection in the edge xv. Since x and v are arbitrary vertices of H, the same is true for all vertices and edges.

Suppose instead that $a + b = c$. Then again, of the four triangles in H, one has all angles a, one b, and one c. The fourth triangle has one angle $a + b = c$, so all angles in the triangle have measure c. At the second angle, where angles a and c meet, we have $c = d - (a + c)$, since $c = a + c$ is impossible. Similarly, at the third angle we have $c = d - (b + c)$. Thus

$$\displaystyle{a = d - 2c\text{ and }b = d - 2c,}$$

so $a = b = d - 2c$. Since $a + b = c$, we have $(d - 2c) + (d - 2c) = c$, so $c = d/5$. In particular, d is divisible by 5. Let u ₁ = u and let u ₂, ⋯u ₅ be vertices in cyclic order about x making consecutive angles of d∕5, so that u ₁⋯u ₅ are invariant under a 5-fold rotation about x. We can assume that u ₂ = v and u ₃ = w. By the 5-fold symmetry about x, there are edges between all the vertices in u ₁, ⋯u ₅, so the subgraph induced by those vertices together with x is a 6-clique and is invariant under 5-fold rotations about any vertex in H and under reflection in any edge.

We claim for the case m = 6, the map M is non-orientable. Suppose not. Let H is a 6-clique and B the subgroup of Aut(M) leaving H invariant. As we have observed, B includes a reflection in each edge and 5-fold rotations about every vertex, so B acts transitively on H with vertex stabilizers D ₅. Thus $\vert B\vert = 6 \cdot 10 = 60$. Let C ⊂ B be the subgroup generated by orientation-preserving automorphisms. Since B contains reflections, C has index two in B, so | C |  = 30. Since C contains the rotations about each of the 6 vertices, it has 24 elements of order 5 and hence is generated by these vertex rotations, which as elements of the symmetric group S ₆ are even permutations. Thus C ⊂ A ₆. Any involution in A ₆ fixes two vertices u, v and hence the edge uv in H. Since | C | is even, it has an involution, but no orientation-preserving automorphism can fix an edge. We conclude that M is not orientable.

We have shown that any K ₄ subgraph H has either all angles measure d∕3 or all measure $d/5,2d/5$. Since any clique of maximal size m has many different K ₄ subgraphs for m > 4, they cannot all have angles d∕3 or $d/5,2d/5$, so the only possibility for m is 4 or 6.

For m = 4, 6, we have described completely the m-cliques containing any vertex v and shown that each edge incident to m is in one and only one clique. Thus the m-cliques give a K _m -factorization of G. □ 

Orientably regular maps with underlying graph K _n have been studied for many years. By the work of Biggs [1] and James and Jones [7] (see also [11]), such maps only occur for n = p ^e for prime p and are in one-to-one correspondence with generators of the cyclic multiplicative group of the finite field GF(p ^e). With this information, it is not hard to show all such maps are chiral except for n = 2². The methods used are entirely algebraic. Theorem B is entirely geometric and provides:

Corollary 2.

Any orientably regular map with underlying graph K _n ,n > 4, is chiral.

Wilson [13] investigated non-orientable regular maps with underlying graph K _n . HIs main result again follows immediately from Theorem B:

Corollary 3.

The only non-orientable regular maps with underlying graph K _n are for n = 3,4,6.

We have assumed that our underlying graph G has no multiple edges. On the other hand, multiple edges arise naturally in an algebraic treatment of maps, as in [3]. Note that loops in G are not an issue when M is regular: by the rotational symmetry at any vertex, if one edge is a loop, then all are, so M has only one vertex. Our result for clique numbers also applies to maps with multiple edges:

Theorem 1.

Let M be any regular map, possibly with multiple edges. Then the clique number of M is 2,3,4,6.

Proof.

Suppose that M is a regular map with multiple edges and automorphism group A. Let the cyclic order of edges incident to vertex v be e ₁, ⋯e _d and let the other endpoint of edge e _i be u _i , for i = 1, ⋯d; if there are multiple edges, the vertices u ₁, ⋯u _d are not all distinct. Let k be the smallest value such that u ₁ = u _k . Then by the rotational symmetry about v, we have $u_{i+k} = u_{i}$ for all i, where subscripts are treated as residues mod d; moreover, u _i ≠ u _j if | i − j |  < k. Let f be the automorphism that rotates about v by the angle of measure k (so f is a rotation about v of order d∕k). Since $u_{i} = u_{i+k}$, then f fixes not only v but all vertices adjacent to v. In addition, since f take e _i at vertex u _i to e _i+k also at vertex u _i , we must have that f also performs a rotation by angle k (of order d∕k) at all vertices adjacent to v. Thus f fixes all vertices and performs a rotation of order d∕k about all vertices.

In particular, the subgroup B generated by f in A is normal, since it fixes all vertices and is normal in A _v for each vertex v. Thus the quotient map M∕B is regular with $Aut(M/B) = A/B$. The underlying graph G∕B for M∕B has the same vertices as G, since f fixes all vertices, and each set of n∕k multiple edges between v and u _i is identified to a single edge. In particular, the clique number of G∕B is the same as the clique number of G. Since M∕B is regular, that clique number is 2, 3, 4, 6. □ 

Note that in the case of multiple edges, the edges incident to v in a particular clique H may not be symmetrically located around v, since we may choose any edge we want from each set of multiple edges.

There are infinitely many regular orientable maps with clique number 4, and their Petrie duals [11] give non-orientable regular maps. For example, the family:

$$\displaystyle{\langle X,Y: X^{3n} = Y ^{3n} = (XY )^{2} = 1,X^{12}Y ^{12} = 1\rangle,}$$

from [3] gives regular maps where the underlying graph G is K ₄ with each edge replaced by n multiple edges. A natural question to ask is whether there are infinitely many with simple underlying graphs. Computer evidence suggests the answer is yes (Conder, personal communication).

There are also infinitely many regular (necessarily non-orientable) maps with clique number 6. Again, from [3], the family:

$$\displaystyle{\langle X,Y: X^{3n} = Y ^{3n} = (XY )^{2} = 1,X^{60}Y ^{60} = 1\rangle,}$$

gives orientably regular, reflexible maps where the underlying graph is the icosahedron with each edge replaced by n multiple edges. There is a natural antipodal automorphism (orientation-reversing involution fixing no vertices) such that the orbit map is regular, non-orientable, with underlying graph K ₆ with each edge replaced by n multiple edges. Again, a natural question to ask is whether there are infinitely many with simple underlying graphs and the computer evidence suggests the answer is again yes (Conder, personal communication).

Theorem B also applies to graphs, rather than maps:

Theorem C.

Let G be a graph and A ⊂ Aut(G) such that the action of each vertex stabilizer A _v on edges incident to v is naturally dihedral. Then the clique number of G is m = 2,3,4,6. If m ≥ 3, then A is vertex-transitive. If m = 4,6, then G has a K _m factorization.

Proof.

Suppose that the clique number is at least 3. We claim that A is vertex-transitive. Indeed, by the dihedral actions of vertex stabilizers, the action of A is edge-transitive. Moreover, G has a triangle uvw, and the dihedral action of A _v reverses the edge uw. Thus for every edge there is an a ∈ A reversing the edge, making A vertex-transitive.

We can then use A to define an angle measure at every vertex that is preserved by A. First, fix a vertex v and choose a generator b of the index-two cyclic subgroup B _v of A _v . Since all other vertex stabilizers are conjugate to A _v and B is characteristic in A _v , we can use conjugates of b to define a cyclic ordering around every vertex that is preserved by A, which can then be used to define angle measure.

The proof then proceeds in exactly the same way as for regular maps. □