Symmetric cubic graphs of small girth

Marston Conder^{1}  Roman Nedela^{2}
Department of Mathematics  Institute of Mathematics
University of Auckland  Slovak Academy of Science
Private Bag 92019 Auckland  975 49 Banská Bystrica
New Zealand  Slovakia
Email: m.conder@auckland.ac.nz  Email: nedela@savbb.sk

Abstract

A graph Γ is symmetric if its automorphism group acts transitively on the arcs of Γ, and s-regular if its automorphism group acts regularly on the set of s-arcs of Γ. Tutte (1947, 1959) showed that every cubic finite symmetric cubic graph is s-regular for some s ≤ 5. We show that a symmetric cubic graph of girth at most 9 is either 1-regular or 2′-regular (following the notation of Djokovic), or belongs to a small family of exceptional graphs. On the other hand, we show that there are infinitely many 3-regular cubic graphs of girth 10, so that the statement for girth at most 9 cannot be improved to cubic graphs of larger girth. Also we give a characterisation of the 1- or 2′-regular cubic graphs of girth g ≤ 9, proving that with five exceptions these are closely related with quotients of the triangle group Δ(2, 3, g) in each case, or of the group ⟨ x, y | x^{2} = y^{3} = [x, y]^{4} = 1 ⟩ in the case g = 8. All the 3-transitive cubic graphs and exceptional 1- and 2-regular cubic graphs of girth at most 9 appear in the list of cubic symmetric graphs up to 768 vertices produced by Conder and Dobcsányi (2002); the largest is the 3-regular graph F570 of order 570 (and girth 9). The proofs of the main results are computer-assisted.

Keywords: Arc-transitive graph, s-regular graph, girth, triangle group, regular map 2000 Mathematics Subject Classifications: 05C25, 20B25.

1 Introduction

By a graph we mean an undirected finite graph, without loops or multiple edges. For a graph Γ, we denote by V (Γ), E(Γ) and Aut(Γ) its vertex set, its edge set and its automorphism group, respectively.

An s-arc in a graph Γ is an ordered (s + 1)-tuple (v_{0}, v_{1}, …, v_{s−1}, v_{s}) of vertices of Γ such that v_{i−1} is adjacent to v_{i} for 1 ≤ i ≤ s, and also v_{i−1} ≠ v_{i+1} for 1 ≤ i < s; in other words, a directed walk of length s which never includes the reverse of an arc just crossed. A graph Γ is said to be s-arc-transitive if Aut(Γ) is transitive on the set of all s-arcs in Γ. In particular, 0-arc-transitive means vertex-transitive, and 1-arc-transitive means arc-transitive, or symmetric. An arc-transitive graph Γ is said to be s-regular if for any two s-arcs in Γ, there is a unique automorphism of Γ mapping one to the other. An s-regular graph (s ≥ 1) is a union of isomorphic s-regular connected graphs and isolated vertices. Hence in what follows, we consider only non-trivial connected graphs. Every connected vertex-transitive graph is regular in the sense of all vertices having the same valency (degree), and when this valency is 3 the graph is called cubic.

1Supported by the Marsden Fund of New Zealand via grant UOA 0412 2Supported by grant VEGA 2/2060/22 of the Slovak Academy of Sciences and grant APVT-51-012502

Tutte [25, 26] proved that every finite symmetric cubic graph is s-regular for some s ≤ 5. The stabiliser of a vertex in any group acting s-regularly on a (connected) cubic graph is isomorphic to the cyclic group ℤ_{3}, the symmetric group S_{3}, the direct product S_{3} × ℤ_{2} (which is dihedral of order 12), the symmetric group S_{4} or the direct product S_{4} ×ℤ_{2}, depending on whether s = 1, 2, 3, 4 or 5 respectively. In the cases s = 2 and s = 4 there are two different possibilities for the edge-stabilisers, while for s = 1, 3 and 5 there are just one each. Taking into account the isomorphism type of the pair consisting of a vertex-stabiliser and an edge-stabiliser, this gives seven classes of arc-transitive actions of a group on a finite cubic graph. These classes correspond also to seven classes of ‘universal’ groups acting arc-transitively on the infinite cubic tree with finite vertex-stabiliser (see [10, 15]). It follows that the automorphism group of any finite symmetric cubic graph is an epimorphic image of one of these seven groups, called G_{1}, G_{2}^{1}, G_{2}^{2}, G_{3}, G_{4}^{1}, G_{4}^{2} and G_{5} by Conder and Lorimer in [6].

We will use the following presentations for these seven groups, as given by Conder and Lorimer in [6] based on the analysis undertaken in [10, 15]:

G_{1} is generated by two elements h and a, subject to the relations h^{3} = a^{2} = 1;

G_{2}^{1} is generated by h, a and p, subject to h^{3} = a^{2} = p^{2} = 1, apa = p, php = h^{−1};

G_{2}^{2} is generated by h, a and p, subject to h^{3} = p^{2} = 1, a^{2} = p, php = h^{−1};

G_{3} is generated by h, a, p, q, subject to h^{3} = a^{2} = p^{2} = q^{2} = 1, apa = q, qp = pq, ph = hp, qhq = h^{−1};

G_{4}^{1} is generated by h, a, p, q and r, subject to h^{3} = a^{2} = p^{2} = q^{2} = r^{2} = 1, apa = p, aqa = r, h^{−1}ph = q, h^{−1}qh = pq, rhr = h^{−1}, pq = qp, pr = rp, rq = pqr;

G_{4}^{2} is generated by h, a, p, q and r, subject to h^{3} = p^{2} = q^{2} = r^{2} = 1, a^{2} = p, a^{−1}qa = r, h^{−1}ph = q, h^{−1}qh = pq, rhr = h^{−1}, pq = qp, pr = rp, rq = pqr;

G_{5} is generated by h, a, p, q, r and s, subject to h^{3} = a^{2} = p^{2} = q^{2} = r^{2} = s^{2} = 1, apa = q, ara = s, h^{−1}ph = p, h^{−1}qh = r, h^{−1}rh = pqr, shs = h^{−1}, pq = qp, pr = rp,

ps = sp, qr = rq, qs = sq, sr = pqrs.

Given a quotient G of one of the seven groups above by some normal torsion-free subgroup, the corresponding arc-transitive graph Γ = (V, E) can be constructed in the the way described in [6]. Let X be the generating set for G consisting of images of the above generators h, a, …, and let H be the subgroup generated by X \ {a}. For convenience, we will use the same symbol to denote a generator and its image. Now take as vertex-set V = {Hg | g ∈ G}, and join two vertices Hx and Hy an edge whenever xy^{−1} ∈ HaH. This adjacency relation is symmetric since HaH = Ha^{−1}H (indeed a^{2} ∈ H) in each of the seven cases. The group G acts on the right cosets by multiplication, preserving the adjacency relation. Since HaH = Ha∪Hah∪Hah^{−1} in each of the seven cases, the graph Γ is cubic and symmetric. This ‘double-coset graph’ will be denoted by Γ = Γ(G, H, a).

Note that in some cases, Aut(Γ) may contain more than one subgroup acting transitively on the arcs of Γ. When G′ is any such subgroup, G′ will be the image of one of the seven groups G_{1}, G_{2}^{1}, G_{2}^{2}, G_{3}, G_{4}^{1}, G_{4}^{2} and G_{5}, and Γ will be obtainable as the double-coset graph Γ(G′, H′, a′) for the appropriate subgroup H′ and element a′ of G′. Such a subgroup G′ of Aut(Γ) will said to be of type 1, 2^{1}, 2^{2}, 3, 4^{1}, 4^{2} or 5, according to which of the seven groups it comes from.

In this paper we investigate symmetric cubic graphs Γ with girth constraints. It turns out that for small g, five of the above seven groups have only finitely many quotients giving rise to symmetric cubic graphs of girth g, with infinite classes arise just from the other two, namely G_{1} and G_{2}^{1}. We find this by systematically enumerating the possibilities for a short relation in the automorphism group G = Aut(Γ), corresponding to a short cycle in the graph Γ. In the five generic groups other than G_{1} and G_{2}^{1}, this gives strong restrictions on the structure of Γ and the group G. The graphs arising from quotients of G_{1} and G_{2}^{1} can be nicely embedded as arc-transitive 3-valent maps on closed surfaces, with the automorphism group of the graph coinciding with the automorphism group of the map; see [9, 14] for example. The exceptional cases (the graphs not arising in this way) can be described case-by-case. It is not surprising that many of these exceptional graphs are well-known, and play important role in other contexts.

Following previous work on this subject, we were motivated by the question about how far we can put a bound on the girth of Γ while maintaining the above distinction between G_{1} and G_{2}^{1} and the other five cases.

It is well known that there are only five connected symmetric cubic graphs with girth less than 6, namely the tetrahedral graph K_{4}, the complete bipartite graph K_{3,3}, the 3dimensional cube graph Q_{3}, the Petersen graph and the dodecahedral graph. This can easily be shown in a case-by-case analysis for girth 3, 4 or 5. Three of these graphs are the one-skeletons of the 3-valent Platonic solids, all embeddable as regular maps on the sphere. The Petersen graph has a symmetric embedding into the real projective plane with six pentagonal faces, while K_{3,3} has a symmetric embedding into the torus with three hexagonal faces. In all these geometrical representations except for the embedding of K_{3,3} in the torus, the girth of the graph is equal to the face size.

The automorphism groups of finite symmetric cubic graphs of girth 6 were studied by Miller [22], who proved that all but finitely many are 2-generator groups of the form

G(s, t, k) = ⟨ x, y | x^{3} = y^{2} = (xy)^{6} = [x, y]^{sk} = (xyx^{−1}y)^{st}(x^{−1}yxy)^{−s} = 1 ⟩,

where s, t and k are positive integers satisfying 0 < 2t ≤ k + 1 and t^{2} − t + 1 ≡ 0(mod k). One can show that apart from the generalised Petersen graph GP (8, 3), all such graphs can be obtained from the triangle group Δ^{+}(6, 3, 2) = ⟨ x, y | x^{3} = y^{2} = (xy)^{6} = 1 ⟩ by first factoring by some normal torsion-free subgroup and then constructing the double-coset graph Γ(G, H, y) where G is the quotient group, and H is the subgroup generated by (the image of) x. It follows that all such graphs except GP (8, 3) are the underlying graphs of 3-valent Coxeter maps on the torus with hexagonal faces.

It was proved in [12] that there are exactly four cubic graphs of girth 6 or 7 that are 3-arc-transitive, namely the Heawood graph, the graph of Pappus configuration, the generalised Petersen graph GP (10, 3), and the Coxeter graph, on 14, 18, 20 and 28 vertices respectively. Also in [23], Morton characterised 4-arc-transitive cubic graphs of girth up to 13, showing that the automorphism group of such a finite graph is either an epimorphic image of the group obtained by adding the relation (ha)^{12} = 1 to the presentation for the group G_{4}^{1}, or otherwise one of nine exceptional graphs. Prior to that, Conder showed in [3] that there are infinitely many 4-arc-transitive finite cubic graphs of girth 12 in the former class, and (somewhat unexpectedly) in [4] that the group obtained by adding the relation (ha)^{12} = 1 to the presentation for the group G_{4}^{1} is isomorphic to an extension by ℤ_{2} of the 3-dimensional special linear group SL(3, ℤ).

In this paper we generalise some of the above results, by classifying symmetric cubic graphs of girth up to 9, and showing that all but finitely many are obtainable from the groups G_{1} and G_{2}^{1}. We also show that the distinction ends there, by describing infinite families of 3-arc-transitive finite cubic graphs of girth 10.

2 Cubic arc-transitive graphs of girth at most 9

Suppose Γ = Γ(G, H, a) is a finite symmetric cubic graph of girth g, obtained by the double-coset construction given in the Introduction. By arc-transitivity, there exists a cycle of length g in Γ containing the vertex H, and of the form

H — Hah^{e_{1}} — Hah^{e_{2}}ah^{e_{1}} — … — Hah^{e_{g}}ah^{e_{g−1}} … ah^{e_{2}}ah^{e_{1}} = H,

where e_{i} = ±1 for 1 ≤ i ≤ g. In particular, ah^{e_{g}}ah^{e_{g−1}} … ah^{e_{2}}ah^{e_{1}} ∈ H, and so we know a relation is satisfied of the form uv^{−1} = 1 where u ∈ H and v = h^{e_{g}}ah^{e_{g−1}} … ah^{e_{2}}ah^{e_{1}} is a word of length m on the two elements ah and ah^{−1}. As H is finite, there are just finitely many such possible relations — indeed at most 48 times 2^{g} (since the largest such H is isomorphic to S_{4} ×Z_{2}, in the 5-arc-transitive case) — and these can be easily enumerated, even up to conjugacy within the relevant group.

Accordingly, to find all finite symmetric cubic graphs of girth at most g, we can take each of the seven groups G_{1}, G_{2}^{1}, G_{2}^{2}, G_{3}, G_{4}^{1}, G_{4}^{2} and G_{5} in turn, and check what happens when each of the possible extra relations of the form uv^{−1} = 1 described above is added to the presentation. If the resulting group G is finite, and of order divisible by the order of the relevant subgroup H, then G will be a group of automorphisms of a graph of the required type, and the same will be true for any quotient of G of order divisible by |H|. On the other hand, if the resulting group G is infinite, then further analysis is required.

We carried out such a systematic search for symmetric cubic graphs of girth at most 11, with the help of the Magma system [1], and carefully inspected the results. More material and some helpful theoretical background on computational group theory can be found in the monograph [24] by Sims. As an illustrative example, in the case of the group G_{4}^{2} we found that up to conjugacy there are only three possible extra relations that give rise to a cycle of length at most 11 in the graph. Two of these are (ha)^{8} = 1 and (ha)^{3}(h^{−1}a)^{3}hah^{−1}a = 1, both giving a quotient of order 720 that acts as a 4-arc-transitive group of automorphisms of Tutte’s 8-cage. The third one is pq(ha)^{2}(h^{−1}a)^{2}ha(h^{−1}a)^{4}ha = 1, which gives a group of order 2160 having the former as a quotient, and acts as a 4-arc-transitive group of automorphisms of a triple cover of Tutte’s 8-cage.

The only quotients that were not immediately found to be finite were some arising from the groups G_{1} and G_{2}^{1}, and others giving graphs of girth 10 or 11. Indeed the results of our search give the following.

Graph s Girth Order Subgroups  Extra relators  Other name
F030 5  8  30  5, 4^{1}, 4^{2}  (hah^{−1}a)^{4}  Tutte 8-cage
F014 4  6  14  4^{1}, 1  (ha)^{6}  Heawood
F102 4  9  102  4^{1}  (ha)^{9}  S(17)
F006 3  4  6  3, 2^{1}, 2^{2}, 1  (ha)^{2}(h^{−1}a)^{2}  K_{3,3}
F010 3  5  10  3, 2^{1}  (ha)^{5}  Petersen
F018 3  6  18 3, 2^{1}, 2^{2}, 1  (ha)^{6}  Pappus
F020B 3  6  20  3, 2^{1}, 2^{2}  pq(ha)^{2}(h^{−1}a)^{2}(ha)^{2}  GP(10,3)
F028 3  7  28  3, 2^{2}  q(ha)^{2}(h^{−1}a)^{2}(ha)^{2}h^{−1}a  Coxeter
F040 3  8  40 3, 2^{1}, 2^{2}, 1  ((ha)^{3}h^{−1}a)^{2}
F056C 3  8  56  3, 2^{1}, 2^{2} (ha)^{8}, pq(ha)^{3}h^{−1}a(ha)^{2}h^{−1}a(ha)^{3} CDC Coxeter
F96B 3  8  96 3, 2^{1}, 2^{2}, 1  ((ha)^{2}(h^{−1}a)^{2})^{2}, (ha)^{12}
F112B 3  8  112 3, 2^{1}, 2^{2}, 1  (ha)^{8}
F192A 3  8  192 3, 2^{1}, 2^{2}, 1  ((ha)^{2}(h^{−1}a)^{2})^{2}
F408B 3  9  408  3, 2^{2}  p(ha)^{2}(h^{−1}a)^{2}(ha)^{2}(h^{−1}a)^{2}ha
F570A 3  9  570  3, 2^{1}  (ha)^{9}

Table 1: Finite 3-, 4- or 5-regular cubic graphs of girth up to 9 Theorem 2.1 There are precisely fifteen finite symmetric cubic graphs of girth up to 9 that are 3-, 4- or 5-regular, as described in Table 1, where the entry in the ‘s’ column indicates that the graph is s-regular, and entries in the ‘Subgroups’ column indicate the types of arc-transitive subgroups in the automorphism group.

Now let us call a finite symmetric cubic graph of girth g exceptional if it is either 3transitive or of type 2^{2}, or if it has type 1 or 2^{1} but its automorphism group is not obtainable from G_{1} or G_{2}^{1} by the addition of a relation of the form (ha)^{g} = 1 or (hah^{−1}a)^{g/2} = 1 (plus other relations as necessary). Note that in the latter cases, the order of (the image) of ha must be greater than g, and the order of (the image of) the commutator hah^{−1}a must be greater than g/2.

Theorem 2.2 There are just five exceptional finite symmetric cubic graphs of type 1 or 2^{1} and girth up to 9, as described in Table 2, where the entry in the ‘s’ column indicates that the graph is s-regular, and entries in the ‘Subgroups’ column indicate the types of arc-transitive subgroups in the automorphism group.

Graph s Girth Order Subgroups  Extra relators  Other name
F016 2  6  16  2^{1}, 1  (ha)^{3}(h^{−1}a)^{3}  GP (8, 3)
F048 2  8  48  2^{1}, 1  (ha)^{4}(h^{−1}a)^{4}  GP (24, 5)
F060 2  9  60  2^{1}, 1  p(ha)^{3}(h^{−1}a)^{3}(ha)^{3}, (ha)^{10}
F240B 2  9  240  2^{1}, 1  p(ha)^{3}(h^{−1}a)^{3}(ha)^{3}, (ha)^{20}
F480A 2  9  480  2^{1}, 1  p(ha)^{3}(h^{−1}a)^{3}(ha)^{3}

Table 2: Exceptional 1- or 2-regular cubic graphs of girth up to 9

Before continuing, we give some additional background. Adding (ha)^{m} = 1 as an extra relator to the presentation for G_{1} or G_{2}^{1}, we obtain the ordinary (2, 3, m) triangle group Δ^{+}(2, 3, m), or the extended (2, 3, m) triangle group Δ(2, 3, m), respectively. Consistent with this notation, we may describe G_{1} as Δ^{+}(2, 3, ∞), and G_{2}^{1} as Δ(2, 3, ∞). Moreover, adding the relation [h, a]^{q} = 1 to the group Δ^{+}(2, 3, m) gives the group

Δ^{+}(2, 3, m; q) = ⟨ h, a | h^{3} = a^{2} = (ha)^{m} = [h, a]^{q} = 1 ⟩.

Again here, each of the parameters m and q may take the value ∞, meaning that the respective element ha or [h, a] is of infinite order. The groups Δ(2, 3, m; q) are defined similarly. The problem of deciding for which parameters m and q the group Δ^{+}(2, 3, m; q) is infinite was investigated in [17] and [11]; the case of Δ^{+}(2, 3, 13; 4) appears to be the only one that is unresolved.

The results of our computations give the following:

Theorem 2.3 Every finite symmetric cubic graph of girth g ≤ 9 is either exceptional (and so listed in one of the Tables 1 and 2 associated with Theorems 2.1 and 2.2), or is isomorphic to a double-coset graph Γ(G, H, a), where G is an epimorphic image of one of the following groups, and H is the image of the cyclic subgroup generated by h in cases (a) and (c), or the dihedral subgroup generated by h and p in case (b):

(a) the (2, 3, g) triangle group ⟨ h, a | h^{3} = a^{2} = (ha)^{g} = 1 ⟩,

(b) the extended (2, 3, g) triangle group ⟨ h, a, p | h^{3} = a^{2} = (ap)^{2} = (hp)^{2} = (ha)^{g} = 1 ⟩,

(c) the group ⟨ h, a | h^{3} = a^{2} = (hah^{−1}a)^{4} = 1 ⟩ ≅ Δ^{+}(2, 3, ∞; 4).

Proof. A computer-assisted enumeration of the possible extra relators that can be added to the presentation for one of the seven groups G_{1}, G_{2}^{1}, G_{2}^{2}, G_{3}, G_{4}^{1}, G_{4}^{2} and G_{5}, corresponding to a girth cycle, shows that the only relators that do not cause the group to collapse to a finite group are the following:

G_{1}: (ha)^{6}, (hah^{−1}a)^{3}, (ha)^{7}, (ha)^{8}, (hah^{−1}a)^{4}, (ha)^{9};

G_{2}^{1}: (ha)^{6}, (hah^{−1}a)^{3}, (ha)^{7}, p(hah^{−1}a)^{3}ha, (ha)^{8}, (hah^{−1}a)^{4}, (ha)^{9}, p(hah^{−1}a)^{4}ha.

The group G_{2}^{1}, however, has an outer automorphism θ taking (h, p, a) to h, p, ap, given by conjugation by an appropriate element of the group G_{3} in which G_{2}^{1} can be embedded (as a subgroup of index 2), and under this automorphism, we see that every relation of the form (ha)^{g} = 1 is equivalent to either (hah^{−1}a)^{g/2} = 1 if g is even, or p(hah^{−1}a)^{(g−1)/2}ha = 1 if g is odd. Hence for G_{2}^{1}, we need only consider extra relators of the form (ha)^{g} for 6 ≤ g ≤ 9, while for G_{1}, we have only (ha)^{g} for 6 ≤ g ≤ 9, and (hah^{−1}a)^{g/2} for g ∈ {6, 8}.

In all other cases, additional of the extra relator gives a finite quotient group of order at most 2880 (for G_{2}^{1}), 6840 (for G_{3}), 2448 (for G_{4}^{1}) or 1440 (for G_{5}), and hence the list of exceptional graphs (the largest of which has order 570), or otherwise a finite quotient that produces a graph that has smaller girth than that given by the length of the extra relator, or a graph that has additional automorphisms and is therefore s-regular for some larger value of s than expected for quotients of the generic group G_{s} or G_{s}^{1} or G_{s}^{2}.

To complete the proof, we now show that the case in which the relator (hah^{−1}a)^{3} is added to the group G_{1}, giving the group Δ^{+}(2, 3, ∞; 3), can be discarded also.

First, we note that in the extended (2, 3, 2k) triangle group Δ(2, 3, 2k), which is just G_{2}^{1} with the relation (ha)^{2k} = 1 added, the elements x = ap and y = h generate a subgroup L of index 2 (with cosets L = Lh and La = Lp, and satisfy the defining relations x^{2} = y^{3} = [x, y]^{k} = 1 (because [x, y] = pah^{−1}aph = aph^{−1}pah = ahah = (ah)^{2}, which has order k). Thus L ≅ Δ(2, 3, ∞; k), whenever k ≥ 3.

When k = 3, the extended (2,3,6) triangle group is known to be a semi-direct product (split extension) of a free abelian normal subgroup N of rank 2 (generated by the commutators ah^{−1}ah and ahah^{−1}) by a dihedral subgroup D of order 12 (generated by the element ha of order 6 in the ordinary triangle group Δ^{+}(2, 3, 6), and the involution ap from Δ(2, 3, 6) \ Δ^{+}(2, 3, 6)). In particular, in this semi-direct product ND = Δ(2, 3, 6), every torsion-free normal subgroup must intersect the dihedral subgroup D trivially, and therefore lies in the normal subgroup N. But also the subgroup L generated by x = ap and y = h (considered above) contains both ah^{−1}ah = (xy)^{2} and ahah^{−1} = (xy^{−1})^{2}, and therefore contains N; indeed L is a semi-direct product of N by a dihedral subgroup of order 6, and hence every torsion-free normal subgroup of the subgroup L lies in N as well. Moreover, conjugation by the element a (lying outside L) takes each of ah^{−1}ah and ahah^{−1} to its inverse, and because N is abelian this induces an automorphism of any subgroup of N, and so any normal subgroup of L contained in N is also normal in the extended triangle group Δ(2, 3, 6).

It follows that every finite symmetric cubic graph that can be constructed from a quotient of L ≅ Δ^{+}(2, 3, ∞; 3) by a torsion-free normal subgroup must actually be 2-arc-transitive, and be constructible from a quotient of Δ(2, 3, 6) by the same normal subgroup. Thus we can eliminate the case of Δ^{+}(2, 3, ∞; 3), as claimed.

The coincidence of normal subgroups of Δ^{+}(2, 3, ∞; 3) and Δ(2, 3, 6) can be interpreted geometrically. A normal subgroup N of finite index in Δ(2, 3, 6) gives rise to a reflexible Coxeter toroidal map M = {6, 3}_{b,c}, with bc(b − c) = 0, in the notation of Coxeter and Moser [9]. The corresponding object obtained from Δ^{+}(2, 3, ∞; 3) using the same normal subgroup N is a Petrie map P (M) of {6, 3}_{b,c}, the boundary walks of which are formed by the (zig-zag) Petrie polygons of M. Both M and P (M) are bipartite maps, with the same underlying graph, and have the same automorphism group Δ(2, 3, 6)/N.

We now turn our attention to case (c) of the above theorem, concerning the family of 1-regular graphs obtainable from quotients of the group Δ^{+}(2, 3, ∞; 4). A computational search has already shown that there are no such graphs with fewer than 400 vertices, and that on up to 768 vertices, there exists just one such graph, namely F400A (see [5]). The following, however, shows that that F400A is just one of infinitely many graphs that arise from case (c) (but not cases (a) or (b)) of Theorem 2.3.

Proposition 2.4 There are infinitely many 1-regular graphs of girth 8 with automorphism group a quotient of Δ^{+}(2, 3, ∞; 4) but not of Δ^{+}(2, 3, 8). The smallest is the 1-regular graph F400A of order 400.

Proof. Let L = Δ^{+}(2, 3, ∞; 4) and G = Δ(2, 3, 8). The automorphism group of the graph F400A is a quotient of L by a torsion-free normal subgroup K of index 1200. This subgroup K is not normal in G, however; its core H = Core_{G}(K) in G has index |K : H| = 25 in K, index |L : H| = 30000 in L, and and index |G : H| = 60000 in G.

On the other hand, the abelianisation K/[K, K] of the subgroup K is free abelian of rank 52 (isomorphic to ℤ^{52}), as can be found by the Reidemeister-Schreier process (implemented as the Rewrite command in Magma [1]). It follows that for every positive integer k, the group L contains a normal subgroup M = [K, K]K^{k} of index k^{52} in K, with quotient L/M of order 1200k^{52}, isomorphic to an extension of an abelian group ℤ_{k}^{52} by the group L/K. If this subgroup M were normal in G, then M would have to contain the core of K in G, and so the order of the quotient G/M would have to be divisible by 60000. This happens only if k^{52} is divisible by 25. Hence if k is not divisible by 5, then the subgroup M = [K, K]K^{k} is not normal in G, and so we get a 1-regular graph of order 1200k^{52} and girth 8 that is not obtainable from the extended (2, 3, 8) triangle group. Since the order of the image of ha in the quotient L/K is 12, the order of its image in the quotient L/M is a multiple of 12, and hence also the corresponding graph is not obtainable from the ordinary (2, 3, 8)-triangle group.

The following proposition shows that our Theorem 2.3 cannot be improved by relaxing the girth constraint. Details can be verified using Magma, or are available from the first author on request.

Proposition 2.5 There are infinitely many finite 3-arc-regular cubic graphs of girth 10, and infinitely many finite 3-arc-regular cubic graphs of girth 11.

Proof. One way to prove this follows from the computational search we conducted for symmetric cubic graphs of girth up to 11, in the case of the group G_{3}.

Adding (ha)^{10} = 1 as an extra relation in the presentation for G_{3} does not give a finite group — indeed the group is infinite, for it has a subgroup L of index 12 with infinite abelianisation L/[L, L] ≅ ℤ_{2} ⊕ ℤ. One such subgroup L is generated by pq and phah^{−1}a. The core of this subgroup is a 5-generator normal subgroup of index 240, and the corresponding quotient is the automorphism group of the 3-regular cubic graph F020B (which is the generalised Petersen graph GP (10, 3)). As in the proof of Proposition 2.4, we can use the Reidemeister-Schreier process to obtain a presentation for the core of L. This is a 5-generator 6-relator group, the abelianisation of which is the free abelian group ℤ^{5} = ℤ ⊕ ℤ ⊕ ℤ ⊕ ℤ ⊕ ℤ of rank 5. Reducing modulo k for any positive integer k gives a characteristic subgroup of index k^{5} in the core, which is then normal in the group we are considering, and hence this group has a quotient of order 240k^{5}. This gives an infinite family of 3-regular cubic graphs, of order 20k^{5} for k = 1, 2, 3, …, each of which is an abelian cover of the graph F020B, and has girth 10.

Similarly, in the group obtained by adding pq(ha)^{2}(h^{−1}a)^{2}(ha)^{2}(h^{−1}a)^{2}(ha)^{2} = 1 as an extra relator to the presentation for G_{3}, there exists a subgroup of index 52 with infinite abelianisation, and the core of this subgroup has index 31200 and abelianisation ℤ^{51}, giving another infinite family of 3-regular cubic graphs of girth 10.

Finally, adding either (ha)^{11} = 1 or q(ha)^{2}(h^{−1}a)^{2}(ha)^{2}(h^{−1}a)^{2}(ha)^{2}h^{−1}a = 1 as an extra relation to G_{3} gives an infinite family of 3-regular cubic graphs of girth 11, and order 1012k^{22}, for k = 1, 2, 3, ….

3 Concluding remarks

It is well-known that the triangle groups Δ^{+}(2, 3, g) and Δ(2, 3, g) act as groups of automorphisms of a 3-valent tessellation by g-gons of the hyperbolic plane, the Euclidean plane or the sphere, according as g > 6, g = 6 or g < 6. The group Δ^{+}(2, 3, g) preserves orientation, while elements of Δ(2, 3, g) \ Δ^{+}(2, 3, g) reverse orientation.

Any quotient of Δ^{+}(2, 3, g) or Δ(2, 3, g) by a torsion-free normal subgroup of finite index therefore gives not just a symmetric 3-valent graph Γ, but also a symmetrical embedding of Γ into a compact closed surface, called respectively an orientably-regular or regular embedding in the literature. It follows from Theorem 2.3 that most of the symmetric cubic graphs of girth at most 9 admit a regular g-gonal embedding.

In fact a 3-valent symmetric graph admits an orientably-regular or regular embedding into some surface (not necessarily g-gonal) if and only if its automorphism group contains an arc-transitive subgroup that is a quotient of G_{1} or G_{2}^{1}, respectively (see [14]). In particular, quotients of Δ^{+}(2, 3, 7) and Δ(2, 3, 7) give rise to the so-called Hurwitz maps. It is well-known that the order of the group G of all orientation-preserving automorphisms of a compact Riemann surface of characteristic χ < 0 is at most −84χ, and at most −168χ when orientation-reversing automorphisms are included, and that this Riemann-Hurwitz bound is achieved if and only if the automorphism group is a quotient of Δ^{+}(2, 3, 7) or Δ(2, 3, 7) respectively; see [19].

Checking the column headed ‘Subgroups’ in our Tables 1 and 2 of exceptional graphs, we find there are only four cubic symmetric graphs of girth at most 9 that admit neither an orientably-regular nor a regular embedding, namely F028, F030, F102, and F408B.

These and the other exceptional cubic graphs (in Tables 1 and 2) have many interesting properties, and were studied in many different contexts. Some of their properties have a nice combinatorial description. There is, of course, exhaustive literature dealing with the Petersen graph (see [16] for example).

Here we say few words on the four exceptional graphs of girth 6, and on the unique exceptional graph of girth 7, which is the Coxeter graph. Further investigation of the exceptional graphs of girth 8 and 9 is beyond the scope of this paper.

For n ≥ 3 and k ∈ ℤ_{n} with 1 ≤ k < n/2, the generalised Petersen graph GP (n, k) is a graph with vertex set {x_{i} | i ∈ ℤ_{n}} ∪ {y_{i} | i ∈ ℤ_{n}}, and edges of the form {x_{i}, x_{i+1}}, {x_{i}, y_{i}} and {y_{i}, y_{i+k}} for all i ∈ ℤ_{n}. It was proved in [13] that GP (n, k) is symmetric if and only if (n, k) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5) or (24, 5).

The generalised Petersen graph GP (8, 3) is the graph F016, which is a double cover of GP (4, 3), the 3-dimensional cube. Accordingly, its automorphism group is isomorphic to a semi-direct product (S_{4} × ℤ_{2}) : ℤ_{2}. The graph is 2^{1}-regular, and the action of its automorphism group determines an octagonal embedding of the graph into the double torus, giving rise to a regular map of genus 2 (see [9, page 29, Fig.3.6c]). More information on this graph can be found in [20].

The generalised Petersen graph GP (10, 3) is the graph F20B, which is a canonical double cover of the Petersen graph, with automorphism group Aut(GP (5, 2)) × ℤ_{2} ≅ S_{5} × ℤ_{2}. This group has 240 elements, so the graph is 3-regular. Since Aut(GP (10, 3)) contains no 1-regular subgroup, GP (10, 3) has no regular embedding into an orientable surface. Since it admits a subgroup acting 2-regularly with an edge stabiliser ℤ_{2} × ℤ_{2}, however, it is the underlying graph of a non-orientable regular map. There are two such maps, both of type {10, 3}, and they are Petrie duals of each other.

Figure 1: Regular embedding of the graph of Pappus configuration in the torus

The Pappus graph 9_{3} is the 3-regular graph F018, being the incidence graph of the Pappus configuration

{123, 456, 789, 147, 258, 369, 158, 348, 267},

which is a union of three parallel classes of lines in the affine geometry AG(2, 3), with exactly one set of three parallel lines missing. The automorphism group of 9_{3} has order 216, and is a semi-direct product of a non-abelian group of order 27 and exponent 3 by a dihedral group of order 8. Another remarkable property of 9_{3} is that it has a hexagonal embedding in the torus, giving rise to a self-Petrie regular map, namely the map {6, 3}_{3,0} in the notation of Coxeter and Moser (see Figure 1).

The Heawood graph F014 is the incidence graph of the Fano plane

P = {123, 345, 156, 147, 257, 367, 246},

with automorphism group P SL(3, 2) : ℤ_{2} ≅ P GL(2, 7). The graph is 4-regular, and also admits a 1-regular action of a subgroup of order 42. There is a well-known hexagonal embedding of the Heawood graph giving rise to a chiral regular map, namely the map {6, 3}_{2,1} in the notation of Coxeter and Moser; see Figure 2.

Figure 2: Orientably-regular embedding of the Heawood graph in the torus

Vertices of the Coxeter graph F028 may be taken as antiflags of the Fano plane P (that is, ordered pairs (p, ℓ) consisting of a line ℓ and a point p not incident to ℓ), and two vertices γ = (p, ℓ) and δ = (q, m) are adjacent if P = ℓ ∪ m ∪ {p, q}. By [2, Theorem 12.3.1], the automorphism group of the Coxeter graph has 336 elements and is isomorphic to P GL(3, 2) : ℤ_{2} ≅ P GL(2, 7). This graph is 3-regular, but its automorphism group contains no subgroup of type 1 or 2^{1}, so it has no regular embedding into a surface; in fact the Coxeter graph is the smallest symmetric cubic graph with this property. It has many other remarkable properties; see [7, 27, 8] for more information.

References

[1] W. Bosma, J. Cannon and C. Playoust, The Magma Algebra System I: The User Language, J. Symbolic Computation 24 (1997), 235–265.

[2] A.E. Brouwer, A.M. Cohen and A. Neumaier, “Distance-regular graphs”, Springer-Verlag, Berlin, 1984.

[3] M. Conder, An infinite family of 4-arc-transitive cubic graphs each with girth 12, Bull. London Math. Soc. 21 (1989), 375–380.

[4] M. Conder, A surprising isomorphism, Journal of Algebra 129 (1990), 494–501.

[5] M. Conder and P. Dobcsányi, Trivalent symmetric graphs up to 768 vertices, J. Combinatorial Mathematics & Combinatorial Computing 40 (2002), 41–63.

[6] M. Conder and P. Lorimer, Automorphism groups of symmetric graphs of valency 3, J. Combin. Theory B 47 (1989), 60–72.

[7] H.S.M. Coxeter, Self-dual configurations and regular graphs, Bull. Amer. Math. Soc. 56 (1950), 413–455.

[8] H.S.M. Coxeter, My graph, Proc. London Math. Soc. (3) 46 (1983), 117–136.

[9] H.S.M. Coxeter and W.O.J. Moser, “Generators and relations for discrete groups”, Springer-Verlag, New York, 1972, third edition.

[10] D.Ž. Djoković and G.L. Miller, Regular groups of automorphisms of cubic graphs, J. Combin. Theory B 29 (1980), 195–230.

[11] M. Edjvet, An example of an infinite group, Discrete Groups and Geometry (Birmingham, 1991), London Math. Soc. Lecture Note Ser., 173, Cambridge Univ. Press, Cambridge, 1992, pp. 66–74.

[12] Y.Q. Feng, R. Nedela, Symmetric cubic graphs of girth at most 7, preprint.

[13] R. Frucht, J.E. Graver, and M.E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971), 211–218.

[14] A. Gardiner, R. Nedela, J. Širáň and M. Škoviera, Characterization of graphs which underlie regular maps on closed surfaces, J. London Math. Soc. 59 (1999), 100–108.

[15] D.M. Goldschmidt, Automorphisms of trivalent graphs, Ann. of Math. 111 (1980), 377–406.

[16] D.A. Holton, S.J. Sheehan, “The Petersen graph”, Cambridge Univ. Press, Cambridge 1993.

[17] J. Howie and R.M. Thomas, The groups (2, 3, p; q); Asphericity and conjecture of Coxeter, J. Algebra 154 (1993), 289–309.

[18] G.A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. London Math. Soc. (3) 37 (1978), 273–307.

[19] A.M. Macbeath, Generators of linear fractional groups, Proc. Sympos. Pure Math., vol. XII, Amer. Math. Soc., Providence, R.I. (1969), 14–32.

[20] D. Marušič and T. Pisanski, The remarkable generalized Petersen graph G(8, 3), Math. Slovaca 50 (2000), 117–121.

[21] G.A. Miller, Groups defined by the orders of two generators and the order of their product, Amer. J. Math. 24 (1902), 96–106.

[22] R.C. Miller, The trivalent symmetric graphs of girth at most six, J. Combin. Theory 10 (1971), 163–182.

[23] M.J. Morton, Classification of 4- and 5-arc-transitive cubic graphs of small girth, J. Austral. Math. Soc. (Ser. A) 50 (1991), 138–149.

[24] C.C. Sims, Computation with finitely presented groups, Cambride Univ. Press, Cambridge 1994.

[25] W.T. Tutte, A family of cubical graphs, Proc. Cambr. Philosoph. Soc. 43 (1947), 459–474.

[26] W.T. Tutte, On the symmetry of cubic graphs, Canad. J. Math. 11 (1959), 621–624.

[27] W.T. Tutte, A non-hamiltonian graph, Canad. Math. Bull. 3 (1960), 1–5.