A more detailed classification of symmetric cubic graphs

Marston Conder^{1}  Roman Nedela^{2}
Department of Mathematics  Mathematical Institute
University of Auckland  Slovak Academy of Sciences
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. Djokovič and Miller (1980) proved that there are seven types of arc-transitive group action on finite cubic graphs, characterised by the stabilisers of a vertex and an edge. A given finite symmetric cubic graph, however, may admit more than one type of arc-transitive group action. In this paper we determine exactly which combinations of types are possible. Some combinations are easily eliminated by existing theory, and others can be eliminated by elementary extensions of that theory. The remaining combinations give 17 classes of finite symmetric cubic graph, and for each of these, we prove the class is infinite, and determine at least one representative. For at least 14 of these 17 classes the representative we give has the minimum possible number of vertices (and we show that in two of these 14 cases every graph in the class is a cover of the smallest representative), while for the other three classes, we give the smallest examples known to us. In an Appendix, we give a table showing the class of every symmetric cubic graph on up to 768 vertices.

Keywords: Arc-transitive graph, s-regular graph, symmetric graph 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 its automorphism group 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. For s ≥ 1, an s-regular graph 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 [20, 21] proved that every finite symmetric cubic graph is s-regular for some s ≤ 5. The stabiliser of a vertex in any group acting regularly on the s-arcs of a (connected) cubic graph is isomorphic to either 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 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 [15, 17]). 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 [11].

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

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 [11]. 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 the coset space 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).

In some cases, the full automorphism group 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. For example, the Petersen graph is 3-regular, with automorphism group S_{5} of order 120 and type 3, but also A_{5} acts regularly on its 2-arcs, with type 2^{1} (since A_{5} contains involutions that reverse an edge). Another way of saying this is that there exists an epimorphism ψ: G_{3} → S_{5} (with torsion-free kernel), and the restriction of ψ to the subgroup G_{2}^{1} (of index 2 in G_{3}) maps G_{2}^{1} to A_{5}. On the other hand, the Sextet graph S(17) constructed in [2] has automorphism group PSL(2, 17) of order 2448 and type 4^{1}, but the simple group PSL(2, 17) contains no proper subgroup of index up to 16, and hence contains no other subgroup acting arc-transitively on S(17). In this case, there is an epimorphism θ: G_{4}^{1} → PSL(2, 17) (with torsion-free kernel), but the restriction of θ to the subgroup G_{1} (of index 8 in G_{4}^{1}) maps G_{1} onto PSL(2, 17).

In this paper we provide a more detailed classification of finite symmetric cubic graphs, by determining exactly which combinations of types are realisable for arc-transitive subgroups of the full automorphism group. Some combinations are easily eliminated by existing theory (such as in [11, 15, 17]), and others will be eliminated by elementary extensions of that theory, in Section 2. The remaining combinations give 17 classes of finite symmetric cubic graph. We provide further general background to some of these in Section 3, and then in Section 4 we give detailed information about each one.

For each of the 17 classes, we give at least one representative, including the absolute smallest in 14 cases, and the smallest known to us in the other three. Also we prove that each class is infinite — in fact in two cases, every graph in the class is a cover of the smallest representative — and we consider the question of whether the graphs in each class are bipartite.

The complete classification is summarised in Section 5, and the class of every finite symmetric graph on up to 768 vertices is given in a table (showing other information about each graph) in an Appendix. We gratefully acknowledge the assistance of the Magma system [3] in the investigations published here.

2 Non-admissible combinations

The following relationships between the seven groups G_{1}, G_{2}^{1}, G_{2}^{2}, G_{3}, G_{4}^{1}, G_{4}^{2} and G_{5} are known, and obtainable from the theory developed in [11, 15, 17].

Proposition 2.1

(a) In the group G_{2}^{1}, the subgroup generated by h and a has index 2 and is isomorphic to G_{1};

(b) The group G_{2}^{2} contains no subgroup isomorphic to G_{1};

(c) In the group G_{3}, the subgroup generated by h, a and pq has index 2 and is isomorphic to G_{2}^{1}, the subgroup generated by h, ap and pq has index 2 and is isomorphic to G_{2}^{2}, and the subgroup generated by h and a has index 4 and is isomorphic to G_{1};

(d) In the group G_{4}^{1}, the subgroup generated by h and a has index 8 and is isomorphic to G_{1}, but there are no subgroups of index 2 isomorphic to G_{3} and no subgroups of index 4 isomorphic to G_{2}^{1} or G_{2}^{2};

(e) In the group G_{4}^{2}, there are no subgroups of index up to 8 isomorphic to G_{1}, G_{2}^{1}, G_{2}^{2} or G_{3};

(f) In the group G_{5}, the subgroup generated by hpq, a and pq has index 2 and is isomorphic to G_{4}^{1}, the subgroup generated by hpq, ap and pq has index 2 and is isomorphic to G_{4}^{2}, and the subgroup generated by h and a has index 16 and is isomorphic to G_{1}, but there are no subgroups of index up to 8 isomorphic to G_{2}^{1}, G_{2}^{2} or G_{3}.

As a consequence of these relationships, we know the following:

Corollary 2.2 Let G be an arc-transitive group of automorphisms of a finite symmetric cubic graph Γ. Then

• if G has type 2^{2}, then G contains no subgroup of type 1;

• if G has type 4^{1}, then G contains no subgroup of type 2^{1}, 2^{2} or 3;

• if G has type 4^{2}, then G contains no subgroup of type 1, 2^{1}, 2^{2} or 3;

• if G has type 5, then G contains no subgroup of type 2^{1}, 2^{2} or 3.

This puts a severe restriction on the combinations of types of that are realisable. For example, no such graph can have arc-transitive subgroups of both the types 2^{2} and 4^{1}; other such conditions are described in detail in [15, Section 6].

Once combinations like {2^{2}, 4^{1}} are eliminated, we are left with just 23 possibilities to consider:

1-arc-regular Γ : {1} only
2-arc-regular Γ : {1, 2^{1}}, {2^{1}}, {2^{2}}
3-arc-regular Γ : {1, 2^{1}, 2^{2}, 3}, {1, 2^{1}, 3}, {1, 2^{2}, 3}, {2^{1}, 2^{2}, 3}, {1, 3}, {2^{1}, 3}, {2^{2}, 3}, {3}
4-arc-regular Γ : {1, 4^{1}}, {4^{1}}, {4^{2}}
5-arc-regular Γ : {1, 4^{1}, 4^{2}, 5}, {1, 4^{1}, 5}, {1, 4^{2}, 5}, {4^{1}, 4^{2}, 5}, {1, 5}, {4^{1}, 5}, {4^{2}, 5}, {5}.

But further, we have:

Proposition 2.3 If the automorphism group of a 3-arc-regular finite cubic graph has an arc-transitive subgroup of type 1 (and index 4), then it also has arc-transitive subgroups of types 2^{1} and 2^{2} (and index 2). Similarly, if the automorphism group of a 5-arc-regular finite cubic graph has an arc-transitive subgroup of type 1 (and index 16), then it also has arc-transitive subgroups of types 4^{1} and 4^{2} (and index 2).

Proof. The first part of this was proved in [15, Proposition 26], but can also be explained as follows. Suppose Γ is a 3-arc-regular finite cubic graph, and ψ : G_{3} → Aut(Γ) is an epimorphism with the property that the restriction of ψ to the subgroup M generated by h and a (of index 4 in G_{3}) maps M to a subgroup G of index 4 in Aut(Γ). Then the action of Aut(Γ) by right multiplication on right cosets of G is equivalent to the corresponding action of G_{3} on cosets of M, namely the following:

\begin{matrix}h & ↦ & (M)(Mp)(Mq)(Mpq), & a & ↦ & (M)(Mp, Mq)(Mpq), \\ p & ↦ & (M, Mp)(Mq, Mpq), & q & ↦ & (M, Mq)(Mp, Mpq). \end{matrix}

The kernel of this action is the subgroup K generated by h and aha, of index 8 in G_{3}, and the quotient G_{3}/K is dihedral. In particular, and since aha = aphpa = (ap)h(ap)^{−1}, the subgroup K is contained in the two subgroups ⟨h, a, pq⟩ and ⟨h, ap, pq⟩ given in Proposition 2.1(c) as isomorphic to G_{2}^{1} and G_{2}^{2} respectively, and these must be taken by ψ to subgroups of index 2 in Aut(Γ). Thus Aut(Γ) contains arc-transitive subgroups of types 2^{1} and 2^{2}.

The case in which Γ is 5-arc-regular is analogous to this one, except the subgroup M generated by h and a has index 16 in G_{5}, and its core K in G_{5} is the subgroup generated by all conjugates of the element (ha)^{4}(h^{−1}a)^{4}ha(h^{−1}a)^{2}(ha)^{2}h^{−1}a and has index 112896. (These facts can be verified with the help of Magma [3].) Since K is contained in the two subgroups ⟨hpq, a, pq⟩ ≅ G_{4}^{1} and ⟨hpq, ap, pq⟩ ≅ G_{4}^{2} given in Proposition 2.1(f), it follows that Aut(Γ) contains arc-transitive subgroups of types 4^{1} and 4^{2}.

This eliminates the possibility of the combinations {1, 2^{1}, 3}, {1, 2^{2}, 3} and {1, 3} for 3regular cubic graphs, and {1, 4^{1}, 5}, {1, 4^{2}, 5} and {1, 5} for 5-regular cubic graphs, leaving just 17 combinations that will all be shown to be realisable in Section 4.

3 Further background on admissible combinations

Many of the possible combinations of types of actions can be seen in the automorphism groups of symmetric cubic graphs of small order. A census of these, including most but not all examples on up to 512 vertices, was compiled by Foster [4], and a complete list of all on up to 768 vertices was obtained systematically by Conder & Dobcsányi [10]. In what follows, we will refer to graphs in the list of all examples of order up to 768 using names consistent with those in [4, 10]; for example, F234B is Wong’s graph, which is the second of the two symmetric cubic graphs of order 234. We have used Magma [3] to help determine the types of action admitted by all the graphs in this list, and the results are given in a table in the Appendix.

Before proceeding further with the classification, we give some general properties of graphs admitting some of the type combinations.

Proposition 3.1 Every symmetric cubic graph admitting actions of types 2^{1}, 2^{2} and 3 is bipartite. On the other hand, every 3-regular cubic graph admitting an action of just one of the types 2^{1} and 2^{2} is non-bipartite.

Proof. The first part of this was proved in [15, Proposition 26] . The group G_{3} has exactly three subgroups of index 2, namely K = ⟨h, a, pq⟩ ≅ G_{2}^{1} and L = ⟨h, ap, pq⟩ ≅ G_{2}^{2} and M = ⟨h, p, q, aha⟩, and any two of these intersect in the normal subgroup ⟨h, pq, aha⟩, of index 4 in G_{3} (with quotient ≅ ⟨a, p⟩ ≅ ℤ_{2} × ℤ_{2}). Now suppose ψ : G_{3} → G is the epimorphism associated with a 3-regular action of a group G on a cubic graph Γ. If K ≅ G_{2}^{1} and L ≅ G_{2}^{2} are both mapped to subgroups of index 2 in G, then these must be different (for otherwise they both contain the ψ-images of all four of h, a, p = a(ap) and q = p(pq)), and so the third subgroup M is also mapped to a subgroup of index 2, in which case Γ is bipartite. Similarly, if just one of the two subgroups K ≅ G_{2}^{1} and L ≅ G_{2}^{2} is mapped to a subgroup of index 2 in G, then M is not, so Γ is non-bipartite.

Proposition 3.2 [15, Proposition 29] Every symmetric cubic graph admitting actions of types 1 and 4^{1} is a cover of the Heawood graph (the incidence graph of a projective plane of order 2), and in particular, is bipartite.

Proof. Let ψ: G_{4}^{1} → G be the epimorphism associated with an action of a group G of type 4^{1} on a cubic graph Γ. If ψ maps the subgroup ⟨h, a⟩ ≅ G_{1} to a subgroup of index 8 in G, then the natural permutation representation of G on cosets of this index 8 subgroup is equivalent to the representation of G_{4}^{1} on cosets of ⟨h, a⟩, which gives PGL(2, 7) as a quotient. Hence ker ψ is contained in the kernel of the latter representation, and it follows that Γ is a cover of the Heawood graph. Since the latter is bipartite, so is Γ.

Proposition 3.3 Every symmetric cubic graph admitting actions of types 4^{1}, 4^{2} and 5 is bipartite. On the other hand, every 5-regular cubic graph admitting an action of just one of the types 4^{1} and 4^{2} is non-bipartite.

Proof. This is entirely similar to the proof of Proposition 3.1. The group G_{5} has exactly three subgroups of index 2, namely K = ⟨h, a, pq⟩ ≅ G_{4}^{1} and L = ⟨h, ap, pq⟩ ≅ G_{4}^{2}, and M = ⟨h, p, q, r, s, aha⟩, with any two of these intersecting in the normal subgroup ⟨h, pq, aha⟩ of index 4 in G_{5} (with quotient ≅ ⟨a, p⟩ ≅ ℤ_{2} × ℤ_{2}). It follows that if ψ: G_{5} → G is the epimorphism associated with a 5-regular action of a group G on a cubic graph Γ, and K ≅ G_{4}^{1} and L ≅ G_{4}^{2} are both mapped to subgroups of index 2 in G, then so is M, so Γ is bipartite. On the other hand, if just one of the two subgroups K ≅ G_{4}^{1} and L ≅ G_{4}^{2} is mapped to a subgroup of index 2 in G, then M cannot be, so Γ is non-bipartite.

Proposition 3.4 Every 5-regular cubic graph admitting actions of types 1 and 5 is a cover of the Biggs-Conway graph (of order 2352), and in particular, is bipartite.

This was recognised by Djokovič and Miller in [15, Proposition 30], although the Biggs-Conway graph itself was not identified until later in [1]. The automorphism group of the Biggs-Conway graph is isomorphic to a subgroup of index 2 in the wreath product PGL(2, 7) ≀ C_{2}, of order 112896. This group has a faithful permutation representation of degree 16 that is equivalent to the action of the group G_{5} on the cosets of subgroup ⟨h, a⟩ ≅ G_{1}, with its three subgroups of index 2 being equivalent to the images of the three subgroups K, L and M considered in the proof of Proposition 3.3.

Proof of 3.4. If ψ: G_{5} → G is the epimorphism associated with a 5-regular action of a group G on on a cubic graph Γ, and ψ maps the subgroup ⟨h, a⟩ ≅ G_{1} to a subgroup of index 16 in G, then the natural permutation representation of G on cosets of this index 16 subgroup is equivalent to the representation of G_{5} on cosets of ⟨h, a⟩, which gives the automorphism group of the Bigg-Conway graph as a quotient. Hence ker ψ is contained in the kernel of the latter representation, and it follows that Γ is a cover of the Bigg-Conway graph. Since the latter is bipartite, so is Γ.

4 Admissible combinations of actions

We consider each of the possible type combinations in turn.

4.1 Type 1 only

Finite cubic graphs admitting arc-transitive group actions of type 1 only are precisely those which are 1-regular. All examples are the underlying graphs of orientably-regular but chiral (irreflexible) 3-valent maps (see [9, 14] or related articles on regular maps).

The smallest is F026, with automorphism group a semi-direct product of Z_{13} by Z_{6} (of order 78), but there are many others, and not every example is a cover of this one. Examples like F026 (of girth 6) are bipartite, but others like F448A (of girth 7) are not.

There are infinitely many graphs in this class. In fact there are at least two different kinds of families of examples. On one hand, there is an infinite family of examples of girth 6 with soluble automorphism groups, obtainable by adding (ha)^{6} = 1 plus extra relations to the group G_{1}; see [19]. On the other hand, it can be shown using coset graphs that for every integer k ≥ 7, all but finitely many of the alternating groups A_{n} can be generated by two elements x and y such that x, y and xy have orders 2, 3 and k respectively, with the additional property that there exists no group automorphism taking x and y to x^{−1} and y^{−1} respectively. This theorem (which will be published elsewhere by the first author in a paper on chiral maps) implies that there exist infinite many 1-regular finite cubic graphs of girth k for every k ≥ 7, with alternating (and therefore insoluble) automorphism groups. Actions of type 2^{1} and 3 are avoided because of chirality — a lack of mirror symmetry — and actions of type 4^{1} and 5 are avoided because PSL(2, 7) is not involved as a composition factor in the automorphism group.

4.2 Types 1 and 2^{1} only

All graphs in this class are 2-regular, and have a 1-regular (but no 3-regular) group of automorphisms. As such, they are all underlying graphs of 3-valent regular maps that are both reflexible and orientable, but not isomorphic to their Petrie duals; see [16].

The smallest is the complete graph K_{4}, but not every example is a cover of this one. Examples like the 3-dimensional cube graph F008 (of girth 4) and F050 (of girth 6) are bipartite, while K_{4} (of girth 3) and F056B (of girth 7) others like these are not.

There are infinitely many graphs in this class. Their automorphism groups are the images of non-degenerate epimorphisms from G_{2}^{1} ≅ PGL(2, ℤ) with the property that the subgroup G_{1} = ⟨h, a⟩ ≅ PSL(2, ℤ) maps to a subgroup of index 2, and there exists no group automorphism taking the images of h, p and a to the images of h, p and ap respectively. As the latter condition can be checked by considering the images of (ha)^{2} and (hap)^{2} = hah^{−1}a, it is relatively easy to verify when (ha)^{2} and hah^{−1}a map to elements of different orders. Examples include the symmetric groups S_{n} for all but finitely many n (see [5]), and PGL(2, q) or PSL(2, q) × Z_{2} for certain prime-powers q (see [6]). Indeed for any integer k ≥ 6, this class contains infinitely many graphs of girth k, by residual finiteness of the (2, 3, k) triangle group ⟨ a, h | a^{2}, h^{3}, (ah)^{k} ⟩.

4.3 Type 2^{1} only

In this class, the graphs are 2-regular but admit no 1-regular group of automorphisms. As such, they are all underlying graphs of non-orientable 3-valent regular maps (see [9]).

The smallest is the graph F084, but not every example is a cover of this one. Examples like F120A (of girth 8) are bipartite, but F084 (of girth 7) and others like it are not.

Again there are infinitely graphs in this class. Their automorphism groups are the images of non-degenerate epimorphisms from G_{2}^{1} ≅ PGL(2, ℤ) under which G_{1} = ⟨h, a⟩ ≅ PSL(2, ℤ) does not map to a subgroup of index 2, and there exists no group automorphism taking the images of h, p and a to the images of h, p and ap respectively. Examples include simple quotients of G_{2}^{1} such as the alternating groups A_{n} for all but finitely many n (see [5]), and PSL(2, p) for certain primes p (see [6]). Note that simplicity implies that there will be no subgroup of type 1, but does not rule out the possibility of the graph being 3-arc-regular (as the Petersen graph shows in §4.7 below).

4.4 Type 2^{2} only

This class consists of 2-regular cubic graphs admitting an action of type 2^{2}. The first known example of such a graph was given by Conder and Lorimer in [11], in answer to a question raised by Djokovič and Miller in [15, Problem 2]. This example had automorphism group S_{11}. The smallest example was found to be F448C, of order 448, in [10]. Clearly not every example is a cover of this smallest one. Both F448C and the earlier example are bipartite, but many others are not. An infinite family of non-bipartite examples (with automorphism groups A_{6k+3} for all k > 3) was constructed in [12, Example 4.1].

4.5 Types 1, 2^{1}, 2^{2} and 3

Graphs in this class are 3-regular cubic graphs admitting an action of type 1 (and therefore actions of types 2^{1} and 2^{2}, by Proposition 2.3). As such, they are the underlying graphs of reflexible orientable 3-valent regular maps that are isomorphic to their Petrie duals.

The smallest example is the complete bipartite graph K_{3,3}, but there are many others, such as F040, which are not covers of this one. All examples are bipartite, by [15, Proposition 26] or Proposition 3.1.

Again there are infinitely graphs in this class; in fact there are infinitely many that are covers of K_{3,3}. To see this, note that the kernel of the epimorphism ψ: G_{3} → Aut(K_{3,3}) is a normal subgroup K of index 72 in G_{3}, generated by conjugates of the element (ha)^{2}(h^{−1}a)^{2}. The Reidemeister-Schreier process (implemented as the Rewrite command in Magma [3]) can be used to show that the abelianisation K/[K, K] of the subgroup K is isomorphic to ℤ^{4} (free abelian of rank 4). It follows that for every positive integer k, the group G_{3} contains a normal subgroup N_{k} = [K, K]K^{k} of index k^{4} in K, with quotient G_{3}/N_{k} of order 72k^{4}, which is then the automorphism group of a 3-regular cubic graph of order 6k^{4} that is a cover of K_{3,3} and admits actions of all four types 1, 2^{1}, 2^{2} and 3.

4.6 Types 2^{1}, 2^{2} and 3 only

Graphs in this class are 3-regular and admit actions of types 2^{1} and 2^{2}, but not of type 1. All such graphs are bipartite, by [15, Proposition 26] or Proposition 3.1. The smallest is F020B, but there are many others, such as F056C, which are not covers of this one.

On the other hand, the class does contain infinitely many covers of F020B. This follows from the fact that the kernel of the epimorphism ψ: G_{3} → Aut(F020B) is a normal subgroup K of index 240 in G_{3}, generated by conjugates of the element pq(ha)^{2}(h^{−1}a)^{2}(ha)^{2}, with abelianisation K/[K, K] isomorphic to ℤ^{11} (free abelian of rank 11). For every positive integer k, the group G_{3} therefore contains a normal subgroup N_{k} = [K, K]K^{k} of index k^{11} in K, with quotient G_{3}/N_{k} of order 240k^{11}, which is then the automorphism group of a 3-regular cubic graph of order 20k^{11} that is a cover of F020B and admits arc-transitive group actions of types 2^{1}, 2^{2} and 3. Moreover, if k is odd, then the subgroup ⟨h, a⟩ ≅ G_{1} of G_{3} must map to the same subgroup as ⟨h, a, pq⟩ ≅ G_{2}^{1} (of index 2 in the automorphism group), so this graph will not admit an arc-transitive group action of type 1.

4.7 Types 2^{1} and 3 only

Graphs in this class are 3-regular and admit actions of type 2^{1}, but not of type 1 or 2^{2}. All such graphs are non-bipartite, by Proposition 3.1. The smallest example is the Petersen graph F010 (see [18]), with automorphism group S_{5}, but there are others that are not covers of this one (such as F570A, the automorphism group of which is PGL(2, 19)).

Again the class is infinite. The kernel of the epimorphism ψ: G_{3} → Aut(F010) is a normal subgroup K of index 120 in G_{3}, generated by conjugates of the element (ha)^{5}. The abelianisation K/[K, K] is isomorphic to ℤ^{6}, so for every positive integer k, the group G_{3} has a quotient of order 120k^{6} that is the automorphism group of a 3-regular cubic graph of order 10k^{6} and contains a subgroup of type 2^{1}. If k is odd, then the subgroup ⟨h, a⟩ ≅ G_{1} of G_{3} must map to the same subgroup as ⟨h, a, pq⟩ ≅ G_{2}^{1} (of index 2 in the automorphism group), while the subgroup ⟨h, ap, pq⟩ ≅ G_{2}^{2} maps onto the full automorphism group, so this graph will not admit an arc-transitive group action of type 1 or 2^{2}.

4.8 Types 2^{2} and 3 only

This case is similar to the previous one, but with the roles of 2^{1} and 2^{2} reversed. Again all graphs in this class are non-bipartite, by Proposition 3.1. The smallest example is the Coxeter graph F028 (see [13]), with automorphism group PGL(2, 7), but there are others that are not covers of this one (such as F408B, the automorphism group of which is PGL(2, 17)).

The class is infinite, for one reason because the epimorphism ψ: G_{3} → Aut(F028) has kernel K of index 336 in G_{3}, generated by conjugates of pha(h^{−1}a)^{2}(ha)^{2}(h^{−1}a)^{2}, with abelianisation K/[K, K] ≅ ℤ^{15}. Accordingly, for every positive integer k, the group G_{3} has a quotient G_{3}/N_{k} of order 336k^{15} that is the automorphism group of a 3-regular cubic graph of order 28k^{15} and contains a subgroup of type 2^{2}; and moreover if k is odd, then the subgroup ⟨h, a⟩ ≅ G_{1} must map to the full automorphism group, so this graph will not admit an arc-transitive group action of type 1 or 2^{1}.

4.9 Type 3 only

Djokovič and Miller found an example in this class in [15, Section 16], having 182 vertices; this is F182D. The smallest example, however, is F110, with automorphism group PGL(2, 11). Clearly not every example is a cover of F110. The two smallest examples are bipartite, but a third small example F506A is not. As in the previous four cases, this class contains infinitely many covers of its smallest member. The kernel of the epimorphism ψ: G_{3} → Aut(F110) is a normal subgroup K of index 1320 in G_{3}, generated by conjugates of q(ha)^{2}(h^{−1}a(ha)^{3})^{2}, with abelianisation K/[K, K] isomorphic to ℤ^{56}. Hence for every positive integer k, the group G_{3} has a quotient G_{3}/N_{k} of order 1320k^{56} that is the automorphism group of a 3-regular cubic graph of order 110k^{56}, and if k is odd, then this graph admits no arc-transitive group action of type 1, 2^{1} or 2^{2}.

4.10 Types 1 and 4^{1} only

As observed by Djokovič and Miller in [15, Proposition 29] (and again in Proposition 3.2 above), there is a unique minimal finite cubic graph admitting actions of types 1 and 4^{1}, namely the Heawood graph F014 (the incidence graph of a projective plane of order 2). Every graph in this class is a cover of the Heawood graph, and in particular, is bipartite. Furthermore, we can show that there are infinitely many such covers. The kernel of the epimorphism ψ: G_{4}^{1} → Aut(F014) is a normal subgroup K of index 336 in G_{4}^{1}, generated by conjugates of p(ha)^{3}(h^{−1}a)^{3}, and the abelianisation K/[K, K] is isomorphic to ℤ^{8}. Hence for every positive integer k, the group G_{4}^{1} has a quotient G_{4}^{1}/N_{k} of order 336k^{8} that is the automorphism group of a 4-regular cubic graph of order 14k^{8} admitting arc-transitive group actions of both types 1 and 4^{1} (but not of type 5, since F014 is not 5-regular).

4.11 Type 4^{1} only

The smallest representative of this class is the Sextet graph S(17) of order 102, labelled F102 in the Foster census, and one of an infinite family of symmetric cubic graphs constructed in [2]. Not every graph in this class is a cover of this smallest one. Examples like F506B (of girth 14) and F650B (of girth 12) are bipartite, but F102 (of girth 9) and others like it are not. This class contains infinitely many of the Sextet graphs S(p), namely all of those for prime p ≡ ±1 mod 16 (in which case S(p) is non-bipartite, with automorphism group PSL(2, p)), and all of those for prime p ≡ ±7 mod 16 but p ≠ 7 (in which case S(p) is bipartite, with automorphism group PGL(2, p)). Also this class contains infinitely many covers S(17), because the kernel of the epimorphism ψ : G_{4}^{1} → Aut(S(17)) is a normal subgroup K of index 2448 in G_{4}^{1}, generated by conjugates of the element (ha)^{9}, with abelianisation K/[K, K] ≅ ℤ^{52}.

4.12 Type 4^{2} only

This class consists of 4-regular cubic graphs admitting an action of type 4^{2}. The first known example of such a graph was a (non-bipartite) graph with automorphism group A_{29}, produced by Conder & Lorimer [11] in answer to a question raised by Djokovič and Miller in [15, Problem 3]. Also an infinite family of (bipartite) examples with automorphism groups S_{36k} for all k > 4 was subsequently constructed in [12, Example 4.2].

The smallest example we have been able to find is a graph of order 27,634,932, which is a 3^{10}-fold cover of F468 (which is itself a double cover of Wong’s graph F234B). The automorphism group of this graph is an extension of an elementary abelian group of order 3^{10} by Aut(PSL(3, 3)), and is isomorphic to the permutation group induced by G_{4}^{2} on the cosets of its subgroup of index 39 generated by the elements p, q, r, a, (ha)^{3}(h^{−1}a)^{2}hah, (ha)^{5}(h^{−1}a)^{3}h and (ha)^{4}h^{−1}aha(h^{−1}a)^{2}hah^{−1}. We do not know for sure if this is the smallest 4-regular cubic graph of type 4^{2}.

4.13 Types 1, 4^{1}, 4^{2} and 5

As observed in [15, Proposition 30] by Djokovič and Miller, and repeated above in Proposition 3.4, there is a unique minimal finite cubic graph admitting actions of types 1 and 5, namely the Biggs-Conway graph [1]. The automorphism group of this graph contains subgroups of index 2 that are the images of the subgroups ⟨h, a, pq⟩ ≅ G_{4}^{1} and ⟨h, ap, pq⟩ ≅ G_{4}^{2} under an epimorphism from G_{5}, as well as a subgroup of index 16 which is the image of the subgroup ⟨h, a⟩ ≅ G_{1}. Accordingly, the graph admits arc-transitive actions of types 1, 4^{1}, 4^{2} and 5. Every finite cubic graph admitting actions of all four of these types is a cover of the Biggs-Conway graph, and in particular, must be bipartite.

Furthermore, we can show that there are infinitely many of these covers. The kernel of the epimorphism from G_{5} to the automorphism group of the Biggs-Conway graph is a normal subgroup K of index 112896 in G_{5}, generated by conjugates of the element (ha)^{4}(h^{−1}a)^{4}ha(h^{−1}a)^{2}(ha)^{2}h^{−1}a, with abelianisation K/[K, K] ≅ ℤ^{1177}. (Note that computation of this abelianisation is not easy because of the large index |G_{5} : K|; but it is relatively easy to see that K is contained in the subgroup L = ⟨h^{−1}aha, hah^{−1}a⟩, which has index 96 in G_{5} and has abelianisation L/[L, L] ≅ ℤ^{2}, and then since [K, K] ⊂ [L, L], it follows that [K, K] has infinite index in L, and therefore infinite index in K.)

4.14 Types 4^{1}, 4^{2} and 5 only

Graphs in this class are 5-regular and admit actions of types 4^{1} and 4^{2}, but not of type 1. All such graphs are bipartite, by Proposition 3.3. The smallest is Tutte’s 8-cage F030, which is the Sextet graph S(3), but there are also many others, such as F468 (the double cover of Wong’s graph), which are not covers of this one.

In fact this class contains the Sextet graph S(p) for every prime p ≡ ±3 or ±5 mod 16. Each such S(p) is 5-regular and bipartite, with automorphism group PΓL(2, p^{2}). The latter group contains three subgroups of index 2, one of which is PGL(2, p^{2}), shown in [2] to be 4-regular on S(p). As S(p) is bipartite, it follows from Proposition 3.3 that its automorphism group contains subgroups of both types 4^{1} and 4^{2} (but no 1-regular subgroup, since S(p) does not cover the Biggs-Conway graph).

Also the kernel of the epimorphism ψ: G_{5} → Aut(S(3)) is a normal subgroup K of index 1440 in G_{5}, generated by conjugates of the element pq(ha)^{4}(h^{−1}a)^{4}, with abelianisation K/[K, K] ≅ ℤ^{16}, so this class contains infinitely many covers of S(3).

4.15 Types 4^{1} and 5 only

For every graph Γ in this class, there is an epimorphism ψ: G_{5} → Aut(Γ) that maps both of the subgroups ⟨h, a⟩ ≅ G_{1} and ⟨h, a, pq⟩ ≅ G_{4}^{1} to a subgroup of index 2 in Aut(Γ), and the subgroup ⟨h, ap, pq⟩ ≅ G_{4}^{2} onto Aut(Γ) itself. Every such graph Γ will be non-bipartite, by Proposition 3.3.

One example is a graph of order 75600 with automorphism group S_{10} shown to exist by Conder in [7], and we believe this is the smallest example.

There are, in fact, infinitely many such examples, because the kernel K of the corresponding epimorphism ψ: G_{5} → S_{10} has infinite abelianisation. The precise form of the abelianisation is difficult to determine, since |G_{5} : K| = 10!, but it is easy to verify (with the help of Magma [3] for example) that K is contained in the subgroup L of index 90 in G_{5} generated by p, ahah^{−1}a, h^{−1}ahah^{−1}ahpahah^{−1}ah^{−1} and hahah^{−1}ahahah^{−1}apahah^{−1}ah^{−1}, and that this has abelianisation L/[L, L] ≅ ℤ_{2} ⊕ ℤ_{2} ⊕ ℤ. Since [K, K] ⊂ [L, L], it follows that [K, K] has infinite index in L, and therefore infinite index in K. Hence this class of graphs contains infinitely many covers of Conder’s graph of order 75600.

Also there are many more examples than these: Conder showed in in [8] how to combine permutation representations for S_{4} × Z_{2} to prove that for all but finitely many n, there exists an epimorphism ψ: G_{5} → S_{n} under which the ψ-images of h and a are permutations generating A_{n} while those of p, q, r and s are odd.

4.16 Types 4^{2} and 5 only

This case is similar to the previous one, but with the roles of 4^{1} and 4^{2} reversed. Again all graphs in this class are non-bipartite, by Proposition 3.3. The smallest is Wong’s graph F234B (see [22]), with automorphism group Aut(PSL(3, 3)), of order 11232. Infinitely many of its covers belong to the same class, as the kernel of the epimorphism ψ: G_{5} → Aut(PSL(3, 3)) has infinite abelianisation (isomorphic to ℤ^{118}). The class contains other examples as well, however, such as one with automorphism group S_{42} (obtainable as the quotient of G_{5} by the core of the subgroup generated by ps, ap and (ha)^{3}h^{−1}ahah^{−1}).

4.17 Type 5 only

The first known graph in this class was an example with automorphism group A_{26}, produced by Conder & Lorimer [11] in answer to a question raised by Djokovič and Miller in [15, Problem 1]. Following on from this, Conder proved in [8] that there are infinitely many such graphs, by showing that examples exist with automorphism group A_{n} for all but finitely many n. (The fact that A_{n} contains no proper subgroup of index less than n implies that there can be no 1- or 4-regular subgroup whenever n > 16.)

These examples are non-bipartite, but there are also infinitely many bipartite examples. The construction presented in [8] can be adapted (by the addition of single extra point) to prove that for all but finitely many n, there exists an epimorphism ψ : G_{5} → S_{n} under which the ψ-images of h, p, q, r and s are even while the ψ-image of a is odd; this epimorphism then maps both ⟨h, a⟩ ≅ G_{1} and ⟨h, ap, pq⟩ ≅ G_{4}^{2} onto S_{n}. The smallest such example has automorphism group S_{20}, but we have been able to find another example, smaller than this, with a rather more interesting group, which we describe below.

The group G_{5} has a subgroup of index 48 generated by the elements h, p, ahahah^{−1}a and qsah^{−1}ah^{−1}aha, the cosets of which are permuted by G_{5} (under multiplication by elements) as follows:

h ↦ (2, 3, 6)(5, 13, 14)(7, 11, 9)(8, 17, 18)(10, 20, 21)(12, 23, 24)(15, 29, 30)(16,

25, 27)(19, 33, 34)(22, 35, 37)(28, 42, 43)(31, 38, 45)(32, 46, 40)(39, 47, 44),

p ↦ (5, 8)(10, 15)(12, 16)(13, 17)(14, 18)(19, 22)(20, 29)(21, 30)(23, 25)(24, 27)

(26, 41)(28, 40)(31, 39)(32, 42)(33, 35)(34, 37)(36, 48)(38, 47)(43, 46)(44, 45),

q ↦ (1, 2)(3, 6)(4, 7)(9, 11)(13, 25)(14, 24)(17, 23)(18, 27)(20, 35)(21, 34)(26, 31)

(28, 32)(29, 33)(30, 37)(36, 43)(38, 44)(39, 41)(40, 42)(45, 47)(46, 48),

r ↦ (1, 3)(2, 6)(4, 11)(5, 12)(7, 9)(8, 16)(10, 19)(14, 27)(15, 22)(18, 24)(21, 37)

(26, 38)(28, 36)(30, 34)(31, 44)(32, 43)(39, 45)(40, 48)(41, 47)(42, 46),

s ↦ (1, 4)(2, 7)(3, 9)(5, 10)(6, 11)(8, 15)(12, 22)(13, 21)(14, 20)(16, 19)(17, 30)

(18, 29)(23, 37)(24, 35)(25, 34)(27, 33)(28, 42)(32, 40)(38, 45)(44, 47),

a ↦ (1, 5)(2, 8)(3, 10)(4, 12)(6, 15)(7, 16)(9, 19)(11, 22)(13, 26)(14, 28)(17, 31),

(18, 32)(20, 36)(21, 38)(23, 39)(24, 40)(25, 41)(27, 42)(29, 43)(30, 44)(33, 46) (34, 47)(35, 48)(37, 45).

These permutations generate a group P isomorphic to the wreath product M_{24} ≀ C_{2} (of order 2|M_{24}|^{2} = 119,876,641,829,683,200), where M_{24} is the simple Mathieu group of degree 24. This group P has just one subgroup of index 2, namely the direct product M_{24} × M_{24}, which is the image of the subgroup ⟨h, aha, p, q, r, s⟩ ≅ G_{4}^{1}. It follows that P is the automorphism group of a bipartite 5-regular cubic graph of order 2,497,430,038,118,400, but contains no subgroup of type 4^{1} or 4^{2}.

The above example was found from a search for subgroups of small index in the group G_{5} using Magma [3], and is the smallest example we have been able to find in this class.

5 Summary

Our findings can be summarised as follows:

Theorem 5.1 Finite symmetric cubic graphs can be classified into 17 different families, according to the combinations of arc-transitive actions they admit. Information on these classes is given in Table 1. In 14 of the 17 classes, the smallest representatives have been determined, and in the other three, the smallest known examples have orders 10! = 75600, 3^{10}·468 and 2^{17}·3^{5}·5^{2}·7^{2}·11^{2}·23^{2} (for the type combinations {4^{1}, 5}, {4^{2}} and {5} respectively). There are infinitely many graphs in each class, and in two cases (the type combinations {1, 4^{1}} and {1, 4^{1}, 4^{2}, 5}) every graph in the class is a cover of the smallest example.

s  Types  Bipartite?  Smallest example  Unique minimal?
1  1  Sometimes  F026  No
2  1,2^{1}  Sometimes  F004 (K_{4})  No
2  2^{1}  Sometimes  F084  No
2  2^{2}  Sometimes  F448C  No
3 1, 2^{1}, 2^{2}, 3  Always  F006 (K_{3,3})  No
3  2^{1}, 2^{2}, 3  Always  F020B (GP(10,3))  No
3  2^{1}, 3  Never  F010 (Petersen)  No
3  2^{2}, 3  Never  F028 (Coxeter)  No
3  3  Sometimes  F110  No
4  1, 4^{1}  Always  F014 (Heawood)  Yes
4  4^{1}  Sometimes  F102 (S(17))  No
4  4^{2}  Sometimes  3^{10}-fold cover of F468?  No
5 1, 4^{1}, 4^{2}, 5  Always  Biggs-Conway graph  Yes
5  4^{1}, 4^{2}, 5  Always  F030 (Tutte’s 8-cage)  No
5  4^{1}, 5  Never  S_{10} graph?  No
5  4^{2}, 5  Never  F234B (Wong’s graph)  No
5  5  Sometimes  M_{24} ≀ C_{2} graph?  No

Table 1: The 17 families of finite symmetric cubic graphs (classified according to the types of arc-transitive group actions admitted)

References

[1] N.L. Biggs, A new 5-arc-transitive cubic graph, J. Graph Theory 6 (1982), 447–451.

[2] N.L. Biggs and M.J. Hoare, The sextet construction for cubic graphs, Combinatorica 3 (1983), 153–165.

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

[4] I.Z. Bouwer (ed.), “The Foster Census”, Charles Babbage Research Centre (Winnipeg, 1988).

[5] M.D.E. Conder, Generators for alternating and symmetric groups, J. London Math. Soc. (2) 22 (1980), 75–86.

[6] M.D.E. Conder, Groups of minimal genus: including C_{2} extensions of PSL(2, q) for certain q, Quart. J. Math. (Oxford) Ser.2 38 (1987), 449–460.

[7] M.D.E. Conder, A new 5-arc-transitive cubic graph, J. Graph Theory 11 (1987), 303–307.

[8] M.D.E. Conder, An infinite family of 5-arc-transitive cubic graphs, Ars Combinatoria 25A (1988), 95–108.

[9] M.D.E. Conder and P. Dobcsányi, Determination of all regular maps of small genus, J. Combin. Theory Ser. B 81 (2001), 224–242.

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

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

[12] M.D.E. Conder and C.E. Praeger, Remarks on path-transitivity in finite graphs, Europ. J. Combinatorics 17 (1996), 371–378.

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

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

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

[16] 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.

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

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

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

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

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

[22] W.J. Wong, Determination of a class of primitive permutation groups, Math. Z. 99 (1967), 235–246.

Appendix: Arc-transitive actions on graphs of order up to 768

Graph Order Automs s-trans Girth Diameter Bipartite?  Types
F004  4  24  2  3  1  No  1, 2^{1}
F006  6  72  3  4  2  Yes  1, 2^{1}, 2^{2}, 3
F008  8  48  2  4  3  Yes  1, 2^{1}
F010  10  120  3  5  2  No  2^{1}, 3
F014  14  336  4  6  3  Yes  1, 4^{1}
F016  16  96  2  6  4  Yes  1, 2^{1}
F018  18  216  3  6  4  Yes  1, 2^{1}, 2^{2}, 3
F020A  20  120  2  5  5  No  1, 2^{1}
F020B  20  240  3  6  5  Yes  2^{1}, 2^{2}, 3
F024  24  144  2  6  4  Yes  1, 2^{1}
F026  26  78  1  6  5  Yes  1
F028  28  336  3  7  4  No  2^{2}, 3
F030  30  1440  5  8  4  Yes  4^{1}, 4^{2}, 5
F032  32  192  2  6  5  Yes  1, 2^{1}
F038  38  114  1  6  5  Yes  1
F040  40  480  3  8  6  Yes  1, 2^{1}, 2^{2}, 3
F042  42  126  1  6  6  Yes  1
F048  48  288  2  8  6  Yes  1, 2^{1}
F050  50  300  2  6  7  Yes  1, 2^{1}
F054  54  324  2  6  6  Yes  1, 2^{1}
F056A  56  168  1  6  7  Yes  1
F056B  56  336  2  7  6  No  1, 2^{1}
F056C  56  672  3  8  7  Yes  2^{1}, 2^{2}, 3
F060  60  360  2  9  5  No  1, 2^{1}
F062  62  186  1  6  7  Yes  1
F064  64  384  2  8  6  Yes  1, 2^{1}
F072  72  432  2  6  8  Yes  1, 2^{1}
F074  74  222  1  6  7  Yes  1
F078  78  234  1  6  8  Yes  1
F080  80  960  3  10  8  Yes  1, 2^{1}, 2^{2}, 3
F084  84  504  2  7  7  No  2^{1}
F086  86  258  1  6  9  Yes  1
F090  90  4320  5  10  8  Yes  4^{1}, 4^{2}, 5
F096A  96  576  2  6  8  Yes  1, 2^{1}
F096B  96  1152  3  8  7  Yes  1, 2^{1}, 2^{2}, 3
F098A  98  294  1  6  9  Yes  1
F098B  98  588  2  6  9  Yes  1, 2^{1}
F102  102  2448  4  9  7  No  4^{1}
F104  104  312  1  6  9  Yes  1
F108  108  648  2  9  7  No  1, 2^{1}
F110  110  1320  3  10  7  Yes  3
F112A  112  672  2  8  7  Yes  1, 2^{1}

Graph Order Automs s-trans Girth Diameter Bipartite?  Types
F112B  112  1344  3  8  10  Yes  1, 2^{1}, 2^{2}, 3
F112C  112  336  1  10  7  Yes  1
F114  114  342  1  6  10  Yes  1
F120A  120  720  2  8  8  Yes  2^{1}
F120B  120  720  2  10  9  Yes  1, 2^{1}
F122  122  366  1  6  9  Yes  1
F126  126  378  1  6  10  Yes  1
F128A  128  768  2  6  11  Yes  1, 2^{1}
F128B  128  768  2  10  8  Yes  1, 2^{1}
F134  134  402  1  6  11  Yes  1
F144A  144  432  1  8  7  Yes  1
F144B  144  864  2  10  8  Yes  1, 2^{1}
F146  146  438  1  6  11  Yes  1
F150  150  900  2  6  10  Yes  1, 2^{1}
F152  152  456  1  6  11  Yes  1
F158  158  474  1  6  11  Yes  1
F162A  162  972  2  6  12  Yes  1, 2^{1}
F162B  162  486  1  12  7  Yes  1
F162C  162  1944  3  12  8  Yes  1, 2^{1}, 2^{2}, 3
F168A  168  504  1  6  12  Yes  1
F168B  168  1008  2  7  9  No  1, 2^{1}
F168C  168  1008  2  8  8  No  1, 2^{1}
F168D  168  1008  2  9  7  No  1, 2^{1}
F168E  168  504  1  12  7  Yes  1
F168F  168  1008  2  12  8  Yes  2^{1}
F182A  182  546  1  6  11  Yes  1
F182B  182  546  1  6  13  Yes  1
F182C  182  1092  2  7  8  No  2^{1}
F182D  182  2184  3  12  9  Yes  3
F186  186  558  1  6  12  Yes  1
F192A  192  2304  3  8  12  Yes  1, 2^{1}, 2^{2}, 3
F192B  192  1152  2  10  10  Yes  1, 2^{1}
F192C  192  1152  2  12  8  Yes  1, 2^{1}
F194  194  582  1  6  13  Yes  1
F200  200  1200  2  6  13  Yes  1, 2^{1}
F204  204  4896  4  12  9  Yes  4^{1}
F206  206  618  1  6  13  Yes  1
F208  208  624  1  10  9  Yes  1
F216A  216  1296  2  6  12  Yes  1, 2^{1}
F216B  216  1296  2  10  9  Yes  1, 2^{1}
F216C  216  1296  2  12  8  Yes  1, 2^{1}
F218  218  654  1  6  13  Yes  1
F220A  220  1320  2  10  9  No  1, 2^{1}
F220B  220  1320  2  10  9  Yes  2^{1}
F220C  220  2640  3  10  10  Yes  2^{1}, 2^{2}, 3

Graph Order Automs s-trans Girth Diameter Bipartite?  Types
F222  222  666  1  6  14  Yes  1
F224A  224  672  1  6  13  Yes  1
F224B  224  1344  2  12  9  Yes  1, 2^{1}
F224C  224  2688  3  12  10  Yes  1, 2^{1}, 2^{2}, 3
F234A  234  702  1  6  14  Yes  1
F234B  234  11232  5  12  8  No  4^{2}, 5
F240A  240  1440  2  8  10  Yes  1, 2^{1}
F240B  240  1440  2  9  10  No  1, 2^{1}
F240C  240  1440  2  10  11  Yes  1, 2^{1}
F242  242  1452  2  6  15  Yes  1, 2^{1}
F248  248  744  1  6  15  Yes  1
F250  250  1500  2  10  10  Yes  1, 2^{1}
F254  254  762  1  6  13  Yes  1
F256A  256  1536  2  8  10  Yes  1, 2^{1}
F256B  256  1536  2  10  10  Yes  1, 2^{1}
F256C  256  1536  2  10  11  Yes  1, 2^{1}
F256D  256  768  1  12  9  Yes  1
F258  258  774  1  6  14  Yes  1
F266A  266  798  1  6  15  Yes  1
F266B  266  798  1  6  15  Yes  1
F278  278  834  1  6  15  Yes  1
F288A  288  1728  2  6  16  Yes  1, 2^{1}
F288B  288  3456  3  12  9  Yes  1, 2^{1}, 2^{2}, 3
F294A  294  1764  2  6  14  Yes  1, 2^{1}
F294B  294  882  1  6  16  Yes  1
F296  296  888  1  6  15  Yes  1
F302  302  906  1  6  15  Yes  1
F304  304  912  1  10  11  Yes  1
F312A  312  936  1  6  16  Yes  1
F312B  312  936  1  12  9  Yes  1
F314  314  942  1  6  17  Yes  1
F326  326  978  1  6  17  Yes  1
F336A  336  2016  2  8  10  Yes  1, 2^{1}
F336B  336  2016  2  8  13  Yes  1, 2^{1}
F336C  336  1008  1  10  12  Yes  1
F336D  336  2016  2  12  9  Yes  1, 2^{1}
F336E  336  2016  2  12  12  Yes  1, 2^{1}
F336F  336  1008  1  12  12  Yes  1
F338A  338  1014  1  6  15  Yes  1
F338B  338  2028  2  6  17  Yes  1, 2^{1}
F342  342  1026  1  6  16  Yes  1
F344  344  1032  1  6  17  Yes  1
F350  350  1050  1  6  17  Yes  1
F360A  360  2160  2  8  11  Yes  2^{1}
F360B  360  4320  3  12  10  Yes  1, 2^{1}, 2^{2}, 3

Graph Order Automs s-trans Girth Diameter Bipartite?  Types
F362  362  1086  1  6  17  Yes  1
F364A  364  2184  2  7  11  No  1, 2^{1}
F364B  364  2184  2  7  12  No  1, 2^{1}
F364C  364  2184  2  7  13  No  1, 2^{1}
F364D  364  2184  2  12  9  No  1, 2^{1}
F364E  364  2184  2  12  9  Yes  2^{1}
F364F  364  2184  2  12  10  Yes  2^{1}
F364G  364  4368  3  12  12  Yes  2^{1}, 2^{2}, 3
F366  366  1098  1  6  18  Yes  1
F378A  378  1134  1  6  18  Yes  1
F378B  378  1134  1  12  10  Yes  1
F384A  384  2304  2  6  16  Yes  1, 2^{1}
F384B  384  2304  2  12  10  Yes  1, 2^{1}
F384C  384  2304  2  12  10  Yes  1, 2^{1}
F384D  384  4608  3  12  12  Yes  1, 2^{1}, 2^{2}, 3
F386  386  1158  1  6  17  Yes  1
F392A  392  1176  1  6  17  Yes  1
F392B  392  2352  2  6  19  Yes  1, 2^{1}
F398  398  1194  1  6  19  Yes  1
F400A  400  1200  1  8  10  Yes  1
F400B  400  2400  2  10  13  Yes  1, 2^{1}
F402  402  1206  1  6  18  Yes  1
F408A  408  2448  2  9  10  No  2^{1}
F408B  408  4896  3  9  10  No  2^{2}, 3
F416  416  1248  1  6  19  Yes  1
F422  422  1266  1  6  19  Yes  1
F432A  432  2592  2  10  12  Yes  1, 2^{1}
F432B  432  2592  2  10  14  Yes  1, 2^{1}
F432C  432  1296  1  12  10  Yes  1
F432D  432  2592  2  12  12  Yes  1, 2^{1}
F432E  432  1296  1  8  12  Yes  1
F434A  434  1302  1  6  17  Yes  1
F434B  434  1302  1  6  19  Yes  1
F438  438  1314  1  6  18  Yes  1
F440A  440  2640  2  10  11  Yes  1, 2^{1}
F440B  440  2640  2  10  12  Yes  1, 2^{1}
F440C  440  5280  3  12  10  Yes  1, 2^{1}, 2^{2}, 3
F446  446  1338  1  6  19  Yes  1
F448A  448  1344  1  7  11  No  1
F448B  448  1344  1  10  13  Yes  1
F448C  448  2688  2  14  10  Yes  2^{2}
F450  450  2700  2  6  20  Yes  1, 2^{1}
F456A  456  1368  1  6  20  Yes  1
F456B  456  1368  1  12  10  Yes  1
F458  458  1374  1  6  19  Yes  1

Graph Order Automs s-trans Girth Diameter Bipartite?  Types
F468  468  22464  5  12  13  Yes  4^{1}, 4^{2}, 5
F474  474  1422  1  6  20  Yes  1
F480A  480  2880  2  9  15  No  1, 2^{1}
F480B  480  2880  2  12  11  Yes  1, 2^{1}
F480C  480  2880  2  12  10  No  1, 2^{1}
F480D  480  2880  2  10  10  Yes  1, 2^{1}
F482  482  1446  1  6  21  Yes  1
F486A  486  2916  2  6  18  Yes  1, 2^{1}
F486B  486  2916  2  12  12  Yes  1, 2^{1}
F486C  486  5832  3  12  12  Yes  1, 2^{1}, 2^{2}, 3
F486D  486  5832  3  12  12  Yes  1, 2^{1}, 2^{2}, 3
F488  488  1464  1  6  19  Yes  1
F494A  494  1482  1  6  19  Yes  1
F494B  494  1482  1  6  21  Yes  1
F496  496  1488  1  10  15  Yes  1
F500  500  3000  2  10  12  No  1, 2^{1}
F504A  504  1512  1  6  20  Yes  1
F504B  504  1512  1  9  10  No  1
F504C  504  3024  2  9  12  No  1, 2^{1}
F504D  504  1512  1  12  12  Yes  1
F504E  504  3024  2  14  10  No  1, 2^{1}
F506A  506  6072  3  11  11  No  3
F506B  506  12144  4  14  10  Yes  4^{1}
F512A  512  3072  2  6  21  Yes  1, 2^{1}
F512B  512  3072  2  10  12  Yes  1, 2^{1}
F512C  512  3072  2  12  11  Yes  1, 2^{1}
F512D  512  3072  2  12  11  Yes  1, 2^{1}
F512E  512  1536  1  14  12  Yes  1
F512F  512  3072  2  8  12  Yes  1, 2^{1}
F512G  512  3072  2  12  10  Yes  1, 2^{1}
F518A  518  1554  1  6  21  Yes  1
F518B  518  1554  1  6  21  Yes  1
F536  536  1608  1  6  21  Yes  1
F542  542  1626  1  6  19  Yes  1
F546A  546  1638  1  6  22  Yes  1
F546B  546  1638  1  6  20  Yes  1
F554  554  1662  1  6  21  Yes  1
F558  558  1674  1  6  22  Yes  1
F566  566  1698  1  6  21  Yes  1
F570A  570  6840  3  9  11  No  2^{1}, 3
F570B  570  3420  2  9  11  No  2^{1}
F576A  576  3456  2  10  16  Yes  1, 2^{1}
F576B  576  1728  1  8  12  Yes  1
F576C  576  3456  2  12  12  Yes  1, 2^{1}
F576D  576  6912  3  12  14  Yes  1, 2^{1}, 2^{2}, 3

Graph Order Automs s-trans Girth Diameter Bipartite?  Types
F578  578  3468  2  6  23  Yes  1, 2^{1}
F582  582  1746  1  6  22  Yes  1
F584  584  1752  1  6  23  Yes  1
F592  592  1776  1  10  15  Yes  1
F600A  600  3600  2  12  12  Yes  1, 2^{1}
F600B  600  3600  2  6  20  Yes  1, 2^{1}
F602A  602  1806  1  6  21  Yes  1
F602B  602  1806  1  6  23  Yes  1
F608  608  1824  1  6  21  Yes  1
F614  614  1842  1  6  23  Yes  1
F618  618  1854  1  6  22  Yes  1
F620  620  14880  4  15  10  No  4^{1}
F624A  624  1872  1  14  12  Yes  1
F624B  624  1872  1  10  16  Yes  1
F626  626  1878  1  6  23  Yes  1
F632  632  1896  1  6  23  Yes  1
F640  640  7680  3  10  12  Yes  1, 2^{1}, 2^{2}, 3
F648A  648  3888  2  6  24  Yes  1, 2^{1}
F648B  648  3888  2  12  14  Yes  1, 2^{1}
F648C  648  3888  2  12  12  Yes  1, 2^{1}
F648D  648  1944  1  12  13  Yes  1
F648E  648  1944  1  12  12  Yes  1
F648F  648  3888  2  12  10  Yes  1, 2^{1}
F650A  650  1950  1  6  23  Yes  1
F650B  650  31200  5  12  11  Yes  4^{1}, 4^{2}, 5
F654  654  1962  1  6  24  Yes  1
F660  660  3960  2  10  11  No  1, 2^{1}
F662  662  1986  1  6  21  Yes  1
F666  666  1998  1  6  22  Yes  1
F672A  672  2016  1  12  12  Yes  1
F672B  672  2016  1  6  24  Yes  1
F672C  672  4032  2  8  12  No  1, 2^{1}
F672D  672  4032  2  12  12  Yes  1, 2^{1}
F672E  672  4032  2  14  12  Yes  1, 2^{1}
F672F  672  4032  2  12  13  Yes  1, 2^{1}
F672G  672  2016  1  12  12  Yes  1
F674  674  2022  1  6  23  Yes  1
F680A  680  8160  3  10  11  No  2^{1}, 3
F680B  680  4080  2  12  10  No  2^{1}
F686A  686  2058  1  6  25  Yes  1
F686B  686  4116  2  12  12  Yes  1, 2^{1}
F686C  686  2058  1  6  23  Yes  1
F688  688  2064  1  10  17  Yes  1
F698  698  2094  1  6  25  Yes  1

Graph Order Automs s-trans Girth Diameter Bipartite?  Types
F702A  702  2106  1  12  14  Yes  1
F702B  702  2106  1  6  24  Yes  1
F720A  720  8640  3  12  12  Yes  1, 2^{1}, 2^{2}, 3
F720B  720  4320  2  8  12  Yes  1, 2^{1}
F720C  720  4320  2  10  10  Yes  1, 2^{1}
F720D  720  2160  1  8  12  Yes  1
F720E  720  4320  2  8  16  Yes  1, 2^{1}
F720F  720  2160  1  10  11  Yes  1
F722A  722  2166  1  6  25  Yes  1
F722B  722  4332  2  6  25  Yes  1, 2^{1}
F726  726  4356  2  6  22  Yes  1, 2^{1}
F728A  728  2184  1  6  23  Yes  1
F728B  728  2184  1  6  25  Yes  1
F728C  728  4368  2  12  12  Yes  1, 2^{1}
F728D  728  4368  2  12  12  Yes  1, 2^{1}
F728E  728  4368  2  12  13  Yes  1, 2^{1}
F728F  728  4368  2  12  14  Yes  1, 2^{1}
F728G  728  8736  3  12  14  Yes  1, 2^{1}, 2^{2}, 3
F734  734  2202  1  6  23  Yes  1
F744A  744  2232  1  12  13  Yes  1
F744B  744  2232  1  6  24  Yes  1
F746  746  2238  1  6  25  Yes  1
F750  750  4500  2  12  12  Yes  1, 2^{1}
F758  758  2274  1  6  25  Yes  1
F762  762  2286  1  6  26  Yes  1
F768A  768  4608  2  10  18  Yes  1, 2^{1}
F768B  768  4608  2  12  11  Yes  1, 2^{1}
F768C  768  4608  2  12  11  Yes  1, 2^{1}
F768D  768  2304  1  12  12  Yes  1
F768E  768  4608  2  12  12  Yes  1, 2^{1}
F768F  768  4608  2  12  13  Yes  1, 2^{1}
F768G  768  4608  2  14  12  Yes  1, 2^{1}