A CENSUS OF SEMISYMMETRIC CUBIC GRAPHS ON UP TO 768 VERTICES

Marston Conder^{1}  Aleksander Malnič^{2}
Department of Mathematics IMFM, Oddelek za matematiko
University of Auckland  Univerza v Ljubljani
Private Bag 92019 Auckland Jadranska 19, 1111 Ljubljana
New Zealand  Slovenija
Dragan Marušič^{2}  Primož Potočnik^{3}
IMFM, Oddelek za matematiko IMFM, Oddelek za matematiko
Univerza v Ljubljani  Univerza v Ljubljani
Jadranska 19, 1111 Ljubljana Jadranska 19, 1111 Ljubljana
Slovenija  Slovenija

Abstract

A list is given of all semisymmetric (edge- but not vertex-transitive) connected finite cubic graphs of order up to 768. This list was determined by the authors using Goldschmidt’s classification of finite primitive amalgams of index (3, 3), and a computer algorithm for finding all normal subgroups of up to a given index in a finitely-presented group. The list includes several previously undiscovered graphs. For each graph in the list, a significant amount of information is provided, including its girth and diameter, the order of its automorphism group, the order and structure of a minimal edge-transitive group of automorphisms, its Goldschmidt type, stabiliser partitions, and other details about its quotients and covers. A summary of all known infinite families of semisymmetric cubic graphs is also given, together with explicit rules for their construction, and members of the list are identified with these. The special case of those graphs having K_{1,3} as a normal quotient is investigated in detail.

1 Introduction

A bipartite regular graph is called semisymmetric if its automorphism group has a single orbit on edges but two orbits on vertices (the two parts of the bipartition).

More generally, given a graph X, let V (X), E(X), A(X) and Aut X be the vertex set, the edge set, the arc set and the automorphism group of X, respectively. If a subgroup G of Aut X acts transitively on V (X), E(X) and A(X), then X is said to be is G-vertex-transitive, G-edge-transitive and G-arc-transitive (or G-symmetric), respectively. It is easily seen that a graph X which is G-edge- but not G-vertex-transitive is necessarily bipartite, with the two parts of the bipartition coinciding with the orbits of G. In particular, if X is a regular graph, then these two parts have equal cardinalities, and such a graph is then referred to as being G-semisymmetric. In the case where G = Aut X the symbol G may be omitted from the definitions above, so that X is called symmetric if it is regular and (Aut X)-arc-transitive, and semisymmetric if it is regular and (Aut X)-edge-transitive but not (Aut X)-vertex-transitive.

2Supported in part by N.Z. Marsden Fund (grant no. UOA 124) and N.Z. Centres of Research Excellence Fund (grant no. UOA 201)

3Supported in part by “Ministrstvo za šolstvo, znanost in šport Slovenije”, research program no.

101-506.

4Supported in part by research projects no. Z1-4186-0101 and no. Z1-3124-0101. The fourth author would like to thank the University of Auckland for hospitality during his visit there in 2003.

The study of semisymmetric graphs was initiated by Folkman [15], who gave a construction of several infinite families of such graphs and posed a number of open problems which spurred the interest in this topic. Several papers followed; see [2, 3, 13, 14, 24, 25, 26, 27, 33, 35].

This article is devoted to the case of cubic (trivalent) semisymmetric graphs. Motivated by the Foster census of arc-transitive cubic graphs on up to 512 vertices [4], the complete determination of all such graphs on up to 768 vertices [7], and the extended Foster census of these up to 998 vertices [6] (incomplete in the range 770-998), we give a complete list of all connected finite semisymmetric cubic graphs of order up to 768. This list contains several previously undiscovered graphs; the third smallest graph on the list, on 112 vertices, is the subject of a separate paper [8].

The construction of this list of semisymmetric cubic graphs was achieved using Goldschmidt’s classification [20] of finite primitive amalgams of index (3, 3). Roughly speaking, an amalgam of index (3, 3) is a pair of groups P_{1} and P_{2} having a common subgroup of index 3 in both, such as the stabilisers in Aut X of the vertices u and v of some edge {u, v} in a cubic graph X. Goldschmidt’s classification implies that the automorphism group of every edge-transitive cubic graph is obtainable as a homomorphic image of the universal completion of one of 15 finite amalgams, denoted by G_{1}, G_{1}^{1}, G_{1}^{2}, G_{1}^{3}, G_{2}, G_{2}^{1}, G_{2}^{2}, G_{2}^{3}, G_{2}^{4}, G_{3}, G_{3}^{1}, G_{4}, G_{4}^{1}, G_{5} and G_{5}^{1}. Each universal completion is essentially an amalgamated free product of the two subgroups P_{1} and P_{2} (with their common subgroup of index 3 amalgamated), and hence has a finite presentation in terms of generators and defining relations. By abuse of notation we use the same symbols (G_{1}, G_{1}^{1}, and so on) to denote these 15 finitely-presented groups, and call each such symbol the Goldschmidt type of the corresponding amalgam.

Note that in all of these 15 finite primitive amalgams of index (3, 3), the orders of the two subgroups P_{1} and P_{2} are at most 384 = 3 · 2^{7}, and it follows that in the automorphism group of any finite connected edge-transitive cubic graph X, the stabiliser of any vertex has order 3 · 2^{s−1} for some s ≤ 8. A now classical theorem of Tutte [37] states that s ≤ 5 in the special case where X is symmetric.

Adopting the same approach as taken in [7] to determine all connected finite symmetric cubic graphs, we used a computerised algorithm for finding all normal subgroups of up to a certain index in each of the 15 finitely-presented groups. In fact again we used the “mixed” version of this algorithm (as explained in [7]), involving coset enumeration over the subgroup P_{1} in each case, so that the upper bound on the index was taken as 768/2 = 384 in each case, in order to obtain all finite homomorphic images representable as an edge-transitive group of automorphisms of some connected finite cubic graph. A more detailed description of this algorithm and unix implementations of it are available from Peter Dobcsányi [12]. The Magma system was used to construct and analyse the resulting graphs, and to determine vertex-transitivity (and hence distinguish between symmetric and semisymmetric cases).

This article is organised as follows. Background material on amalgams (including a table showing the 15 types of primitive amalgam of index (3, 3)) is given in Section 2, followed by some basic theory of quotients and covering projections in Section 3. A brief summary of all known semisymmetric cubic graphs (together with a number of new constructions of such graphs) is given in Section 4. In Section 5, a more detailed analysis of one of these families is undertaken, namely of those semisymmetric cubic graphs having K_{1,3} as a normal quotient. The list itself is presented in Section 7, including detailed information on several graph- and group-theoretic parameters for each of the graphs, and is preceded by some explanation in Section 6. Finally in Section 8 we show how some of the graphs in the list can be obtained as covers of smaller symmetric cubic graphs using voltage constructions.

For general background on graphs and groups, as well as for the concepts and notation not defined here, we refer the reader to [10, 19, 21, 38].

2 Amalgams of index (3,3)

Following [20], an amalgam is a pair (ϕ_{1}, ϕ_{2}) of group monomorphisms ϕ_{1} : B → P_{1} and ϕ_{2} : B → P_{2} with the same domain B. The amalgam is said to be finite if the codomains P_{1} and P_{2} are finite. The pair (|P_{1} : imϕ_{1}|, |P_{2} : imϕ_{2}|) of indices is called the index of the amalgam. The amalgam is said to be primitive if for each i ∈ {1, 2} and for each non-trivial subgroup K of B such that ϕ_{3−i}(K) is normal in P_{3−i}, the normaliser of ϕ_{i}(K) in P_{i} is ϕ_{i}(B). Two amalgams (ϕ_{1} : B → P_{1}, ϕ_{2} : B → P_{2}) and (ϕ′_{1} : B′ → P′_{1}, ϕ′_{2} : B′ → P′_{2}) are isomorphic if there exist group isomorphisms α: B → B′, α_{1} : P_{1} → P′_{1} and α_{2} : P_{2} → P′_{2}, making the obvious diagrams commutative.

A completion of the amalgam (ϕ_{1}, ϕ_{2}) is a pair of group homomorphisms (ψ_{1} : P_{1} → G, ψ_{2} : P_{2} → G) into the same group G, such that ψ_{1} ∘ ϕ_{1} = ψ_{2} ∘ ϕ_{2}, and such that the images of ψ_{1} and ψ_{2} generate G. If ψ_{1} and ψ_{2} are monomorphisms, then the completion is said to be faithful. The completion is called finite if the group G is finite. For every amalgam (ϕ_{1} : B → P_{1}, ϕ_{2} : B → P_{2}), there is a so-called universal completion (ψ_{1}^{∘}: P_{1} → G^{∘}, ψ_{2}^{∘}: P_{2} → G^{∘}) with the following defining property: for every completion (ψ_{1} : P_{1} → G, ψ_{2} : P_{2} → G) of (ϕ_{1}, ϕ_{2}) there exists a group homomorphism α: G^{∘} → G, such that ψ_{i} = α ∘ ψ_{i}^{∘} for i = 1, 2. The group G^{∘} is usually called the amalgamated product of P_{1} and P_{2} (with amalgamated subgroup B), and denoted by P_{1} ∗_{B} P_{2}. In particular, every faithful finite completion can be obtained from the universal completion by taking as the kernel of α some normal subgroup of finite index in G^{∘} that intersects ψ_{i}^{∘}(P_{i}) trivially for i = 1, 2.

Now let (ψ_{1} : P_{1} → G, ψ_{2} : P_{2} → G) be a faithful, finite completion of a finite amalgam (ϕ_{1} : B → P_{1}, ϕ_{2} : B → P_{2}). By abuse of notation, we may identify the groups B, P_{1} and P_{2} with their images in G. We then define the graph of the completion as the bipartite graph X = X(G, P_{1}, P_{2}) with vertex set V the union of the two (right) coset spaces [G : P_{1}] and [G : P_{2}], and with adjacency given by P_{1}g ∼ P_{2}h if and only if P_{1}g∩P_{2}h is non-empty. It is easy to see that the group G acts (via right multiplication) as a group of automorphisms of X, and that this action is transitive on edges but not on vertices; moreover, this action is faithful if and only if core_{G}(B) = _{g∈G}^{∩} g^{−1}Bg = 1, which is equivalent to the primitivity of the amalgam (ϕ_{1}, ϕ_{2}).

Note that the valence of any vertex P_{i}g is |P_{i} : B|, for i = 1, 2. This implies that the graph of a faithful finite completion of a finite amalgam of index (3, 3) is a cubic G-semisymmetric graph, with stabilisers of any two adjacent vertices isomorphic to P_{1} and P_{2} in some order. The converse of this fact together with the classification of all finite primitive amalgams of index (3, 3) achieved in [20, Theorem A] is crucial for our analysis of semisymmetric cubic graphs:

Proposition 2.1 Let X be a finite cubic G-semisymmetric graph other than K_{3,3}. Let {u, v} be any edge of X, and let G_{u} and G_{v} be the stabilisers in G of u and v respectively. Then the pair (ψ_{1} : G_{u} → G, ψ_{2} : G_{v} → G) of inclusion maps is a faithful finite completion of the finite primitive amalgam (ϕ_{1}, ϕ_{2}), of index (3, 3), given by the inclusion maps of the intersection G_{u} ∩ G_{v} into G_{u} and G_{v} respectively, and X is isomorphic to the graph of this completion.

Theorem 2.2 [20, Theorem A] There are precisely fifteen isomorphism classes of finite primitive amalgams of index (3, 3). The corresponding fifteen universal completions are given in Table 1.

Table 1: Universal completions of finite primitive amalgams of index (3, 3)

Type Universal completion
G_{1}  ⟨ x, y | x^{3}, y^{3} ⟩

P_{1} = ⟨x⟩ ≅ ZZ_{3}, P_{2} = ⟨y⟩ ≅ ZZ_{3}, B = {1}

G_{1}^{1}  ⟨ c, x, y | c^{2}, x^{3}, y^{3}, (cx)^{2}, (cy)^{2} ⟩

P_{1} = ⟨c, x⟩ ≅ S_{3}, P_{2} = ⟨c, y⟩ ≅ S_{3}, B = ⟨c⟩ ≅ ZZ_{2}

G_{1}^{2}  ⟨ c, x, y | c^{2}, x^{3}, y^{3}, (cx)^{2}, [c, y] ⟩

P_{1} = ⟨c, x⟩ ≅ S_{3}, P_{2} = ⟨c, y⟩ ≅ ZZ_{6}, B = ⟨c⟩ ≅ ZZ_{2}

G_{1}^{3}  ⟨ c, d, x, y | c^{2}, d^{2}, [c, d], x^{3}, y^{3}, (cx)^{2}, [d, x], [c, y], (dy)^{2} ⟩

P_{1} = ⟨c, d, x⟩ ≅ D_{12}, P_{2} = ⟨c, d, y⟩ ≅ D_{12}, B = ⟨c, d⟩ ≅ ZZ_{2} × ZZ_{2}

G_{2}  ⟨ c, d, x, y | c^{2}, d^{2}, [c, d], x^{3}, y^{3}, (cx)^{2}, [d, x], (cy)^{3}, dy^{−1}cy ⟩

P_{1} = ⟨c, d, x⟩ ≅ D_{12}, P_{2} = ⟨c, d, y⟩ ≅ A_{4}, B = ⟨c, d⟩ ≅ ZZ_{2} × ZZ_{2}

G_{2}^{1}  ⟨ c, d, x, y | c^{2}, d^{4}, (cd)^{2}, x^{3}, (cx)^{2}, [d, x], y^{3}, (dy^{−1})^{2}, cydy ⟩

P_{1} = ⟨c, d, x⟩ ≅ D_{24}, P_{2} = ⟨c, d, y⟩ ≅ S_{4}, B = ⟨c, d⟩ ≅ D_{8}

G_{2}^{2}  ⟨ c, d, x, y | c^{2}, d^{4}, (cd)^{2}, x^{3}, [c, x], [d^{2}, x], d^{−1}xdx, y^{3}, (dy^{−1})^{2}, cydy ⟩

P_{1} = ⟨c, d, x⟩ ≅ ZZ_{3} ⋊ D_{8}, P_{2} = ⟨c, d, y⟩ ≅ S_{4}, B = ⟨c, d⟩ ≅ D_{8}

G_{2}^{3}  ⟨ c, d, e, x, y | c^{2}, d^{2}, e^{2}, [c, d], [c, e], [d, e], x^{3}, (cx)^{2}, [d, x], [e, x], y^{3}, [c, y], y^{−1}cdye, (ye)^{3} ⟩

P_{1} = ⟨c, d, e, x⟩ ≅ D_{12} × ZZ_{2}, P_{2} = ⟨c, d, e, y⟩ ≅ A_{4} × ZZ_{2}, B = ⟨c, d, e⟩ ≅ ZZ_{2} × ZZ_{2} × ZZ_{2}

G_{2}^{4}  ⟨ c, d, e, x, y | c^{2}, d^{4}, e^{2}, (cd)^{2}, [c, e], [d, e], x^{3}, [ce, x], [d, x], (ex)^{2}, y^{3}, (dy^{−1})^{2}, cydy, [y, e] ⟩

P_{1} = ⟨c, d, e, x⟩ ≅ D_{8} × S_{3}, P_{2} = ⟨c, d, e, y⟩ ≅ S_{4} × ZZ_{2}, B = ⟨c, d, e⟩ ≅ D_{8} × ZZ_{2}

G_{3}  ⟨ c, d, x, y | c^{2}, d^{4}, (cd)^{2}, x^{3}, (dx^{−1})^{2}, cxdx, y^{3}, (dy^{−1})^{2}, cdyd ⟩

P_{1} = ⟨c, d, x⟩ ≅ S_{4}, P_{2} = ⟨c, d, y⟩ ≅ S_{4}, B = ⟨c, d⟩ ≅ D_{8}

G_{3}^{1}  ⟨ c, d, e, x, y | c^{2}, d^{4}, e^{2}, (cd)^{2}, [c, e], [d, e], x^{3}, (dx^{−1})^{2}, cxdx, [x, e], y^{3},

(dy^{−1})^{2}, cd^{−1}ydy, [y, ed^{2}] ⟩ P_{1} = ⟨c, d, e, x⟩ ≅ S_{4} × ZZ_{2}, P_{2} = ⟨c, d, e, y⟩ ≅ S_{4} × ZZ_{2}, B = ⟨c, d, e⟩ ≅ D_{8} × ZZ_{2}

G_{4}  ⟨ a, b, s, x, y | a^{4}, b^{4}, s^{2}, [a, b], sasb^{−1}, sbsa^{−1}, x^{3}, x^{−1}axb^{−1}, x^{−1}bxba,

(xs)^{2}, y^{3}, y^{−1}absysa^{2}, y^{−1}sa^{2}yba^{−1}, a^{−1}sysay ⟩ P_{1} = ⟨a, b, s, x⟩ of order 96, P_{2} = ⟨a, b, s, y⟩ of order 96, B = ⟨a, b, s⟩ of order 32

G_{4}^{1}  ⟨ a, b, s, t, x, y | a^{4}, b^{4}, s^{2}, t^{2}, [a, b], sasb^{−1}, sbsa^{−1}, (ta)^{2}, (tb)^{2}, [s, t], x^{3}, x^{−1}axb^{−1},

x^{−1}bxba, (xs)^{2}, [x, t], y^{3}, y^{−1}absysa^{2}, y^{−1}sa^{2}yba^{−1}, a^{−1}sysay, tytsa^{2}y^{−1}a^{2}s ⟩ P_{1} = ⟨a, b, s, t, x⟩ of order 192, P_{2} = ⟨a, b, s, t, y⟩ of order 192, B = ⟨a, b, s, t⟩ of order 64

G_{5}  ⟨ a, b, s, t, x, y | a^{4}, b^{4}, s^{2}, t^{2}, [a, b], sasb^{−1}, (ta)^{2}, (tb)^{2}, [s, t], x^{3}, x^{−1}axb^{−1}, x^{−1}bxba, (xs)^{2},

[x, t], y^{3}, y^{−1}absyba^{−1}, y^{−1}sa^{2}ysb^{−1}a^{−1}, y^{−1}tsa^{2}yb^{−1}a^{−1}, y^{−1}abyb^{−1}ast, tb^{−1}ybty ⟩ P_{1} = ⟨a, b, s, t, x⟩ of order 192, P_{2} = ⟨a, b, s, t, y⟩ of order 192, B = ⟨a, b, s, t⟩ of order 64

G_{5}^{1}  ⟨ a, b, s, t, v, x, y | a^{4}, b^{4}, s^{2}, t^{2}, v^{2}, [a, b], sasb^{−1}, (ta)^{2}, (tb)^{2}, [s, t], vavb^{−2}a^{−1}, vbva^{−2}b,

(vs)^{2}t, [v, t], x^{3}, x^{−1}axb^{−1}, x^{−1}bxba, (xs)^{2}, [x, t], [x, v], y^{3}, y^{−1}absyba^{−1}, y^{−1}sa^{2}ysb^{−1}a^{−1}, y^{−1}tsa^{2}yb^{−1}a^{−1}, y^{−1}abyb^{−1}ast, tb^{−1}ybty, b^{−1}tvbtvtb^{3}a^{2}tb^{−1}, [vtb, y] ⟩ P_{1} = ⟨a, b, s, t, v, x⟩ of order 384, P_{2} = ⟨a, b, s, t, v, y⟩ of order 384, B = ⟨a, b, s, t, v⟩ of order 128

3 Quotients and coverings

In order to facilitate easier reading, we give a short account on quotient projections, and regular covering projections in particular. (For a more extensive treatment of coverings, see [23, 31, 32] for example.)

Quotients and coverings We say that two graph morphisms f: X → X̄ and f′: X′ → X̄′ are isomorphic, written f ≅ f′, if there exist graph isomorphisms α: X → X′ and ᾱ: X̄ → X̄′ such that ᾱ ∘ f = f′ ∘ α. (We tacitly assume that graph morphisms are composed on the \underline{left}, with composition written as ∘. However, graph automorphisms are occasionally composed on the \underline{right}; this is indicated by juxtaposition, that is, by using no special sign for the composition.) If X = X′ and α = id we call f ≅ f′ an equivalence below X (or just equivalence from below). If X̄ = X̄′ and ᾱ = id we call f ≅ f′ an equivalence above X̄ (or just equivalence from above).

Let X be a graph and N ≤ Aut X. The quotient graph X_{N} has the vertex orbits {[v] : v ∈ V (X)} of N as the vertex set, the arc orbits {[a] : a ∈ A(X)} as the arc set (and hence the edge orbits {[e] : e ∈ E(X)} as the edge set), and the adjacencies in X_{N} are defined in a natural way so that the mappings v ↦ [v] and a ↦ [a] on vertices and arcs (and hence e ↦ [e] on edges) define a graph epimorphism q_{N}: X → X_{N}, the quotient projection by the action of N. (Note that X_{N} may have multiple edges, loops or even semiedges — a semiedge is created whenever two inverse arcs of X are in the same orbit of N.) By abuse of terminology, any graph epimorphism q: X → X̄ which is equivalent below X to a quotient projection q_{N}: X → X_{N} is also called a quotient projection and often identified with q_{N} – although a quotient projection might arise from several distinct groups; this fact is a source of many anomalies to be discussed further below.

The kernel of a quotient projection q_{N}: X → X_{N} is the largest subgroup Ker q_{N} ≤ Aut X having the same orbits as the group N. This group is uniquely defined and Ker q_{N} = {α ∈ Aut X | q_{N} ∘ α = q_{N}}. Thus, q_{N} = q_{N′} if and only if Ker q_{N} = Ker q_{N′} (for instance, we do have q_{N} = q_{N′} whenever N ≤ N′ ≤ Kerq_{N}, but the converse might fail to be true). Also, two quotient projections q_{N} and q_{N′} defined on a graph X are isomorphic if and only if Ker q_{N} and Ker q_{N′} are conjugate subgroups of Aut X; in particular q_{N} and q_{N′} are equivalent below X if and only if q_{N} = q_{N′}. Finally, q_{N} is an isomorphism if and only if N is the trivial group (because Aut X acts faithfully on the set of arcs).

Let X be a graph. We say that a group N ≤ Aut X acts semiregularly on X if it acts semiregularly on the vertex set V (X) and on the arc set A(X). The respective quotient projection X → X_{N} is called a regular N-covering projection and is usually denoted by ℘_{N}. If N belongs to some specific class of groups such as cyclic, elementary abelian etc., then the respective regular covering covering projection is also called cyclic, elementary abelian etc. By abuse of terminology, any graph epimorphism ℘: X → X̄ which is equivalent below X to a regular N-covering projection ℘_{N}: X → X_{N} is itself called a regular covering projection (and often identified with ℘_{N}). Note that the group CT(℘) = N = Ker ℘, also known as the group of covering transformations, is now uniquely determined by ℘. This is one of the many nice properties that regular covering projections share and which makes them rather distinguished among quotient projections in general. Another such (characteristic) property is the following: for each arc starting at [v] ∈ V (X_{N}) and each vertex u ∈ [v], there exists a unique arc in X starting at u which projects to the selected arc in X_{N} — this property extends to walks and it is known as the unique walk lifting property; in other words: a quotient projection is a regular covering projection if and only if it is valency preserving.

A regular covering projection ℘: X → X̄ can be reconstructed from X̄, up to equivalence above X̄, as follows. Consider CT(℘) = N as an abstract group, now called the voltage group. In each vertex fibre ℘^{−1}(v̄), v̄ ∈ V (X̄), choose a vertex and label it by 1 ∈ N. Then transfer the labelling by the action of N (considered as a group of automorphisms of X acting on the left) to all the vertices of X. Let ā ∈ A(X̄). Then there exists an element ζ(ā) ∈ N, called the voltage of ā, such that all arcs in the arc fibre ℘^{−1}(ā) over ā ∈ A(X̄) have origins and termini labelled by g and g ζ(ā), where g ∈ N. Obviously, inverse arcs receive inverse voltages. The graph Cov(X; ζ) with vertex set V (X̄) × N and edge set E(X̄) × N = {{(ū, g), (v̄, g ζ(ā)} | ā ∈ A(X̄) with origin ū and terminus v̄, g ∈ N} is isomorphic to X. Obviously, N acts by left multiplication on the second coordinate as a group of automorphisms of Cov(X̄; ζ), and gives rise to a regular covering projection ℘_{ζ} = ℘_{N}: Cov(X̄; ζ) → X̄ which is equivalent above X̄ to ℘: X → X̄. As an abstract voltage group, N acts by right multiplication on itself as the set of labels. It is well known that the voltages can be assigned in such a way that the arcs of an arbitrary chosen spanning tree of X̄ receive the trivial voltage.

Conversely, given a graph X̄, an abstract group N, and a voltage assignment ζ: A(X̄) → N such that the inverse arcs receive inverse voltages, the construction of Cov(X̄; ζ) as above gives a regular covering projection ℘_{ζ} = ℘_{N}: Cov(X̄; ζ) → X̄. The only inconvenience with ζ being arbitrary is that the resulting derived graph might be disconnected. The additional “if and only if” condition which should be imposed on ζ such that Cov(X̄; ζ) is connected, is well known: each element of N should appear as the voltage of some closed walk. If we assume that the arcs of an arbitrarily chosen spanning tree carry the trivial voltage then the derived covering graph is connected if and only if the voltages of the “off-tree arcs” generate the group N.

Projecting and lifting automorphisms Let H ≤ Aut X. We say that H projects along q_{N}: X → X_{N} if, for each h ∈ H, there exists an automorphism h̄ ∈ Aut X_{N} such that h̄ ∘ q_{N} = q_{N} ∘ h, called the projection of h along q_{N}. Note that if h̄ exists then it is unique. So if H projects then we have a naturally defined group H̄ ≤ Aut X_{N}, the projection of H along q_{N}, and we have an induced group epimorphism q_{N}^{∗}: H → H̄, taking h ↦ h̄. We say that G ∈ Aut X_{N} lifts along q_{N} if there exists a group H ≤ Aut X which projects to G, that is, H̄ = G. The largest group that projects onto G is called the lift of G along q_{N} and is denoted by G̃ (such a group is unique). In particular, the kernel Ker q_{N} is the lift of the trivial group.

If a group H ≤ Aut X normalizes N, then H projects along q_{N}, and the groups H/(H ∩ N) and H̄ have the same permutation representation on X_{N}; but the action of H/(H ∩ N) might not be faithful. On the other hand, H may project even if H does not normalize N. In particular, N might not be a normal subgroup of Ker q_{N}. These anomalies are not present with regular covering projections, since Ker ℘_{N} = N in their case.

Proposition 3.1 Let X be a graph and N ≤ Aut X. Then a group H ≤ Aut X projects along q_{N}: X → X_{N} if and only if H normalizes Ker q_{N}. In particular, the largest group that projects along q_{N} is the normalizer of Ker q_{N} within Aut X.

Moreover, if a group H ≤ Aut X projects, then the kernel of the induced group epimorphism q_{N}^{∗}: H → H̄ is H ∩ Ker q_{N}. In particular, if G ≤ Aut X_{N} lifts, then the kernel of the group epimorphism G̃ → G is Ker q_{N}.

A quotient projection q_{N}: X → X_{N} is called normal if Aut X projects along q_{N}, that is, if Ker q_{N} ◁Aut X. In general, if H projects along q_{N} then a conjugate subgroup α ∘ H ∘ α^{−1} projects along q_{(α∘N∘α^{−1})} (which might not be equal to q_{N}). From Proposition 3.1 it follows that, given a graph X and H ≤ Aut X, one can find all quotient projections q_{K}: X → X_{K} along which H projects — by letting K run through all normal subgroups of all subgroups H′ ≤ Aut X containing H. (The resulting projections are not necessarily pairwise distinct, nonequivalent or nonisomorphic; we do find all morphisms, but not necessarily all groups realising these morphisms.) Among these, all regular covering projections are obtained by selecting those subgroups K which act semiregularly on X.

If an automorphism lifts along a quotient projection then it lifts along any quotient projection equivalent to it from above. Consequently, if a regular covering projection ℘_{N}: X → X̄ is reconstructed as ℘_{ζ}: Cov(X̄; ζ) → X̄, then a necessary and sufficient condition for G ≤ Aut X̄ to lift along ℘_{N} can be expressed combinatorially in terms of voltages (in order for G to lift along ℘_{ζ}). Also, it is enough to require that each automorphism in some generating set of G lifts; see Proposition 3.2 below. Equivalence and isomorphism of regular covering projections can also be studied along these lines; see Proposition 3.3 below.

Proposition 3.2 An automorphism α ∈ Aut X̄ lifts along a regular covering projection ℘_{ζ}: Cov(X̄; ζ) → X̄ if and only if each closed walk with trivial voltage is mapped to a walk with trivial voltage.

Proposition 3.3 Regular covering projections ℘_{N_{i}}: Cov(X̄; ζ_{i}) → X̄, for i = 1, 2, are isomorphic if and only if there exists a group isomorphism τ: N_{1} → N_{2} and a graph automorphism α ∈ Aut X̄ such that for each closed walk W in X̄ we have τ(ζ_{1}(W)) = ζ_{2}(α(W)). In particular, ℘_{N_{1}} and ℘_{N_{2}} are equivalent from above if and only if there exists an isomorphism τ: N_{1} → N_{2} such that τ ∘ ζ_{1} = ζ_{2}.

Decomposition of quotient projections We say that a quotient projection q_{N}: X → X_{N} has a decomposition if it can be written as q_{N} = q_{M} ∘ q_{K} where N, K ≤ Aut X and M ≤ Aut X_{K}. Such a decomposition is said to be nontrivial if neither of the projections q_{K} or q_{M} is an isomorphism.

Observe that the K-orbits are contained in the orbits of N if and only if Ker q_{K} ≤ Ker q_{N}. Consequently, a necessary condition for a nontrivial decomposition of q_{N} to exist is that there be a subgroup 1 ≠ K ≤ Ker q_{N} such that Ker q_{K} < Ker q_{N}. But the condition is not sufficient. Specifically, if the K-orbits are contained in the orbits of N, then one can define a graph morphism f: X_{K} → X_{N} such that q_{N} = f ∘ q_{K}, however, this morphism does not necessarily arise from taking the quotient by the action of some group of automorphisms of X_{K}. Now suppose that Ker q_{K} < Ker q_{N} is normalized by N, that is, let N project along q_{K}. Then the projection N̄ ≅ N/(N ∩ Ker q_{K}) of N along q_{K} projects along f; in fact, the graph epimorphism f is isomorphic to the projection qN̄. Such a decomposition is called strong. In particular, if Ker q_{K} is a nontrivial proper normal subgroup of Ker q_{N}, then the decomposition is nontrivial and strong. But if a nontrivial decomposition is strong, then Ker q_{K} is not necessarily a normal subgroup of Ker q_{N}, that is, Ker q_{N} might not project along q_{K}.

Regular covering projections are much better behaved with respect to the questions addressed above. We point out, firstly, that any decomposition ℘_{N} = ℘_{M} ∘ ℘_{K} (where all projections are required to be reqular covering projections) is necessarily strong. Secondly, since N = Ker ℘_{N} and K = Ker q_{K}, we see that K must be normal in N, and consequently, such a decomposition takes the form ℘_{N} = ℘_{N/K} ∘ ℘_{K}. Also, a decomposition is trivial if and only if K = 1 or K = N.

We close this section by introducing some additional terminology for later reference. If ℘_{N}: X → X_{N} is a regular covering projection and a group G ≤ X_{N} lifts along ℘_{N} we say that ℘_{N} is G-admissible. If ℘_{N} is G-admissible but there exists no G-admissible regular covering projection ℘_{N/K} such that ℘_{N} = ℘_{N/K} ∘ ℘_{K}, then we say that ℘_{N} is minimally G-admissible. Loosely speaking, ℘_{N} is minimally G-admissible whenever G lifts along ℘_{N} but does not lift along any “smaller” regular covering projection which decomposes ℘_{N}. We also remark that if ζ denotes the voltage assignment realising ℘_{N}, then the voltage assignment which realises, up to equivalence, the covering projection ℘_{N/K} (such that ℘_{N} = ℘_{N/K} ∘℘_{K}), is given by q∘ζ, where q: N → N/K is the quotient projection. Further details on decomposing quotient and regular covering projections will be given in Section 6.

4 Families of cubic semisymmetric graphs

In this section we give an overview of known families of cubic semisymmetric graphs. With the exception of families I, II and VII, they all arise as regular covers of certain cubic arc-transitive graphs of small orders.

Let n be an integer such that there exists a unique cubic semisymmetric graph on n vertices. We use the symbol Sn to denote this graph. As a natural extension of this notation we use the symbols Sna, Snb, … in the case when nonisomorphic cubic semisymmetric graphs on n vertices exist. For example, the smallest cubic semisymmetric graph, the so called Gray graph on 54 vertices, is denoted with symbol S54, while the three pairwise non-isomorphic cubic semisymmetric graphs on 336 vertices are denoted with symbols S336a, S336b and S336c. The proposed notation is analogous to that used in the Foster census [4] for cubic arc-transitive graphs on n vertices, namely Fn (or Fna, Fnb, …).

I. Let n ≥ 9 be an integer divisible by 3, let A_{n} denote the alternating group acting on the set {1, 2, …, n}, and let α, β ∈ A_{n} be the following permutations:

α = (1, 2, 3)(4, 5, 6)(7, 8, 9) ⋯ (n − 2, n − 1, n),
β = (1, 2, 6)(4, 5, 9)(7, 8, 12) ⋯ (n − 5, n − 4, n)(3)(n − 2)(n − 1).

Then the Cayley graph of A_{n} relative to the generating set {α, β} is the line graph of a cubic semisymmetric graph of order n!/3 (see [33]). The vertex stabilisers are all isomorphic to S_{3} and so the Goldschmidt type is G_{1}^{1}. The smallest graph in the family has 60480 vertices.

II. Two families of cubic semisymmetric graphs given in [28] can be defined using the amalgam completion construction described in Section 2. Namely, let G = P GL(2, p) for p a prime congruent to 11 or 13 modulo 24 and let G = P SL(2, p) for a prime p congruent to ±1 modulo 24. Then G contains a subgroup P_{1} isomorphic to D_{24}, and a maximal subgroup P_{2} isomorphic to S_{4}, which generate G and intersect in a subgroup B isomorphic to D_{8}. The pair of inclusion maps from B into P_{1} and P_{2} is a finite primitive amalgam of index (3, 3) and type G_{2}^{1} (see 2.2). Moreover, the pair of inclusion maps from P_{i}, for i = 1, 2, into G is its faithful finite completion. As observed by Goldschmidt [20], the graph of this completion is a cubic G-semisymmetric graph. The semisymmetry of these graphs was proved in [28]. The smallest members, arising for primes p = 11, 13, 23, are the three biprimitive graphs in our list: S110, S182 and S506. Note that other graphs in these two families are not biprimitive (since the group P_{1} ≅ D_{24} is not maximal in G). But as P_{2} ≅ S_{4} is maximal in G, the action of G on one part of bipartition is primitive in all cases.

III. The next two families arise as covers of K_{3,3} with a cyclic or elementary abelian voltage group N. In order to describe them via voltage assignments we choose the spanning tree carrying trivial voltages as shown in Figure 1. Furthermore, let a, b, c, d ∈ N be the voltages of the remaining cotree arcs (3, 2), (3, 4), (2, 5) and (4, 5), respectively.

Figure 1.

Let n = 3^{ε}p_{1}^{e_{1}}p_{2}^{e_{2}} … p_{k}^{e_{k}}, k ≥ 2, where ε ∈ {0, 1} and p_{i}, i = 1, …, k, are distinct primes congruent to 1 modulo 3, and let N = ZZ_{n}. In this case there are two solutions r, s ∈ ZZ_{n}^{∗} of the equation x^{2} + x + 1 = 0 such that r ≠ s, s^{−1}. Then, letting a = 1, b = −r, c = s, and d = −rs, the corresponding regular N-cover of K_{3,3} is semisymmetric with vertex stabilisers isomorphic to ZZ_{3} (see [30]). Hence the Goldschmidt type is G_{1}. The smallest graph in this family has 546 vertices, appearing in the list as S546a.

Along similar lines, let p ≡ 1(mod 3) be a prime, let N = ZZ_{p}^{2}, and let r ∈ ZZ_{p} be a primitive third root of unity. Then, by letting a = (1, 0), b = (0, 1), c = (r, 0) and d = (0, r), the corresponding regular N-cover of K_{3,3} is semisymmetric (see [29]). We note that vertex stabilisers are isomorphic to S_{3} for p > 7, and so the Goldschmidt type is G_{1}^{1} in such cases. On the other hand, p = 7 gives rise to the smallest graph in the family on 294 vertices, appearing in the list as S294. Its Goldschmidt type is G_{1}^{2}.

IV. There are four infinite families of pairwise nonisomorphic regular elementary abelian covers of the Heawood graph (F14), where the maximal lifted subgroup acts semisymmetrically on the covering graph. The first two families arise, respectively, as ZZ_{p}^{3}-covers and ZZ_{p}^{5}-covers for p ≡ 1, 2 or 4 (mod 7), whereas the remaining two arise as ZZ_{p}^{4}-covers when p satisfies the additional condition p ≡ 1(mod 3). Furthermore, there are three sporadic examples of regular ZZ_{7}^{6}-covers of F14 satisying the above-mentioned property. The minimal members of the first two families are the graphs S112 and S448 in the list. Their Goldschmidt type is G_{1}. We remark that for the remaining graphs the semisymmetry of the full automorphism group has not yet been verified.

In order to describe these constructions, we let the arcs of the Hamilton path 5, 0′, 6, 1′, …, 3, 5′, 4, 6′ of F14 carry the trivial voltage, and we let a_{7}, a_{0}, a_{1}, …, a_{6} denote the voltages of the arcs (5, 6′), (0, 4′), (1, 5′), (2, 6′), (3, 0′), (4, 1′), (5, 2′), (6, 3′), respectively (see Figure 2). To obtain the three ZZ_{7}^{6}-covers, let a_{7} = (1, 0, 0, 0, 0, 0), a_{0} = (0, 1, 0, 0, 0, 0), …, a_{4} = (0, 0, 0, 0, 0, 1) be the six standard basis vectors of ZZ_{7}^{6}, and let a_{5} = (x, 1, 2, 3, 4, 5) and a_{6} = (y, 5, 4, 3, 2, 1), where (x, y) = (6, 6), (3, 2) or (0, 5), respectively. The corresponding three covering graphs on 14 · 7^{6} = 1647086 vertices arise from pairwise non-isomorphic covering projections.

For the remaining infinite families, the prime p satisfies the condition p ≡ 1, 2 or 4 (mod 7). In this case there exists an element s ∈ ZZ_{p} satisfying s^{2} + s + 2 = 0. The infinite family of ZZ_{p}^{3}-covers is obtained by letting a_{7} = (0, 0, 0), a_{0} = (1, 0, 0), a_{1} = (0, 1, 0), a_{2} = (0, 0, 1), a_{3} = (1, s + 1, s), a_{4} = (s, −1, −1), a_{5} = (−1, −1, −s − 1), and a_{6} = (−s − 1, −s, 1). Similarly, the infinite family of ZZ_{p}^{5}-covers is obtained by letting a_{7} = (1, 0, 0, 0, 0), a_{0} = (0, 1, 0, 0, 0), a_{1} = (0, 0, 1, 0, 0), a_{2} = (0, 0, 0, 1, 0), a_{3} = (0, 0, 0, 0, 1) be the standard basis vectors of ZZ_{p}^{5}, and by setting a_{4} = (s, −1, −s, 1, s+1), a_{5} = (s, −s − 1, 1, 1, s), and a_{6} = (−1, −s, 1, s + 1, −1). Finally, let p satisfy the additional condition p ≡ 1(mod 3) and let r_{1}, r_{2} be the two primitive cube roots of unity in ZZ_{p}. Then the two infinite families of ZZ_{p}^{4}-covers are obtained for i = 1, 2 by letting a_{7} = (r_{i} + 3, 0, 0, 0), a_{0} = (1, 1, 0, 0), a_{1} = (1, 0, 1, 0), a_{2} = (1, 0, 0, 1), a_{3} = (−r_{i} − 2, 1, s + 1, s), a_{4} = (−r_{i} − 2, s, −1, −1), a_{5} = (1, −1, −1, −s − 1) and a_{6} = (1, −s − 1, −s, −1).

Figure 2.

V. Apart from the graph S144, with Goldschmidt type G_{1}^{1}, which is a regular ZZ_{3}^{2}- cover of the Moebius-Kantor graph (F16), there is an infinite family of regular elementary abelian covers of F16 where the maximal lifted subgroup acts semisymmetrically on the covering graphs. These graphs arise as ZZ_{p}^{2}-covers, where p ≡ 1 (mod 4) is a prime. The smallest graph in this family is S400. Its Goldschmidt type is G_{1}. As in IV above, the semisymmetry of the full automorphism group for the remaining graphs in the family has not been verified.

Figure 3.

In order to describe these constructions we observe that F16 is isomorphic to the generalised Petersen graph GP (8, 3), thus allowing us to identify its vertex set with ZZ_{8} × ZZ_{2} and its edge set with

E = {{(i, 0), (i+1, 0} | i ∈ ZZ_{8}}∪{{(i, 1), (i+3, 1)} | i ∈ ZZ_{8}}∪{{(i, 0), (i, 1)} | i ∈ ZZ_{8}}.

Define the voltages on the arcs of the inner cycle and on the spokes to be trivial. As for the arcs of the oriented outer cycle, we define these to be, respectively, (1, 0), (0, 1), (0, 1), (−1, 0), (−1, 0), (0, −1), (0, −1), (1, 0), in the case p = 3. Similarly, for the infinite family of regular ZZ_{p}^{2}-covers, p ≡ 1 (mod 4), we let the above voltages be, respectively, (1, 0), (0, 1), (r, r − 1), (0, −r), (−1, 0), (0, −1), (−r, −r − 1), (0, r), where r^{2} = −1. (see Figure 3.)

VI. There exists an infinite family of regular elementary abelian covers of the Pappus graph (F18) where the maximal lifted subgroup acts semisymmetrically on the covering graph. The graphs in this family arise as ZZ_{p}^{2}-covers, where p ≡ 1 (mod 3) is a prime. With the exception of the smallest graph (p = 7), which has 882 vertices and is indeed semisymmetric, the semisymmetry of the full automorphism group for the remaining graphs in the family has not been verified.

Figure 4.

To describe this construction we identify the vertex set of F18 with {1, 2, …, 18} and its edge set with the union of the sets {{i, i+1} | i ∈ {1, 2, …, 18}}, {{i, i+5} | i ∈ {1, 7, 13}}, {{i, i + 7} | i ∈ {2, 8, 14}}, and {{i, i + 7} | i ∈ {4, 10, 16}}, where the arithmetic is performed modulo 18. We let the arcs of the Hamilton path (1, 2, …, 18) carry trivial voltages (see Figure 4), and we let the arcs {(i, i + 5) | i ∈ {1, 7, 13}}, {(i, i + 7) | i ∈ {2, 8, 14}}, {(i, i + 7) | i ∈ {4, 10, 16}}, and (18, 1), respectively, have the following voltages: (1, 0), (1, 0), (1, 0), (0, 1), (−r + 1, r), (−1, −r − 1), (−r, r + 1), (2, −1), (−2, −r), and (−r − 3, 0), where r is an element of order 3 in ZZ_{p}^{∗}.

VII. There are eight graphs in the list with the tripod K_{1,3} as a normal quotient: S120, S330, S336b, S336c, S504, S546b, S660 and S720b. These graphs may be obtained using a general approach described in the next section.

5 Semisymmetric actions arising from K_{1,3}

In this section we prove a theorem which enables us to construct several infinite families of semisymmetric cubic graphs. It deals with the situation where a semisymmetric group of automorphisms contains a normal simple subgroup acting transitively on one part of the bipartition and intransitively on the other. It came to our notice while preparing the final version of this paper that a similar problem was considered by Giudici, Li and Praeger [17].

First we prove the following, which relies heavily on the analysis and classification of finite arc-transitive cubic graphs by Tutte[37] and Djoković and Miller [11], and on an in-depth analysis of their automorphism groups in terms of generators and relations by Conder and Lorimer [5]. In particular, it is known that an arc-transitive group of automorphisms of a finite cubic graph X acts regularly on the set of k-arcs of X for some k ∈ {1, 2, 3, 4, 5}, and its action falls into one of seven possible classes, denoted in [5] by G_{1}, G_{2}^{1}, G_{2}^{2}, G_{3}, G_{4}^{1}, G_{4}^{2} and G_{5}. We shall call these classes Djoković-Miller classes, to distinguish them from the Goldschmidt types of semisymmetric group actions.

Proposition 5.1 Let X be a connected cubic bipartite graph admitting an arc-transitive action of a group G ≤ Aut X, and a semisymmetric action of a subgroup H ≤ G. Also let T be the maximal subgroup of G preserving both parts of the bipartition of X. If H is self-normalising in G, that is, if N_{G}(H) = H, then H is of Goldschmidt type G_{1}, and G belongs to the Djoković-Miller class G_{4}^{2}, and the permutation representation induced by T (by right multiplication) on right cosets of H is isomorphic to the natural action of P SL(2, 7) on the projective line P G(1, 7).

Proof. The proof is divided into several cases, dealing in turn with the seven possible Djoković-Miller classes to which G might belong. It follows from [5] that in each of these cases, the group G is generated by an element h (of order 3) fixing a vertex v, an element a (of order 2 or 4) reversing an arc (v, w) incident with v, and up to four involutions (denoted by p, q, r and s) which generate the stabiliser of the arc (v, w). Also the vertex-stabilisers G_{v} and G_{w} are generated by the stabiliser of the arc (v, w) and elements h and h^{a} = a^{−1}ha, respectively. Moreover, since the order of G_{v} divides 3 · 2^{4} (by Tutte’s theorem), all cyclic subgroups of order 3 fixing the vertex v are conjugate in G_{v}.

We consider possibilities for H in terms of two elements x and y, each of order 3 in H, and stabilizing v and w respectively. Without loss of generality we may suppose that x is the element h used as a generator for G. Furthermore, since v^{a} = w we know that aya^{−1} fixes v, and therefore also aya^{−1} is an element of order 3 in G_{v}.

Now if G belongs to one of the Djoković-Miller classes G_{1}, G_{2}^{1} or G_{2}^{2}, then |T_{v}| = |G_{v}| = 3 or 6, so the index |T : H| = |T_{v} : H_{v}| is either 1 or 2, and hence H is normal in T, contradicting the assumption N_{G}(H) = H.

If G belongs to the Djoković-Miller class G_{3}, then G_{v} ≅ S_{3} × C_{2} is generated by h and two involutions p and q such that pq = qp, php = h, qhq = h^{−1} and ap = qa, and a itself is an involution. Clearly, G_{v} has only two elements of order 3, so aya^{−1} = h or h^{−1}. In both cases, the group ⟨h, h^{a}⟩ = ⟨x, y⟩ ≤ H has index dividing 4 in T with transversal a subset of {1, p, q, pq}. Since N_{G}(H) = H, the index of H in T is at least 4. It follows that H = ⟨h, h^{a}⟩, but this subgroup is normalised by a, contradiction.

If G belongs to the Djoković-Miller class G_{4}^{1} or to the class G_{4}^{2}, then G_{v} ≅ S_{4} is generated by h and three involutions p, q and r such that pq = qp, pr = rp, (qr)^{2} = p, h^{−1}ph = q, h^{−1}qh = pq, rhr = h^{−1}, ap = pa and aq = ra, with a^{2} = 1 in the case of Djoković-Miller class G_{4}^{1}, while a^{2} = p in the case of Djoković-Miller class G_{4}^{2}. This time we find that G_{v} has eight elements of order 3, and so aya^{−1} = h^{±1} or ph^{±1}p or qh^{±1}q or qph^{±1}pq. Thus H contains one of the four subgroups L_{1} = ⟨h, a^{−1}ha⟩, L_{2} = ⟨h, a^{−1}phpa⟩, L_{3} = ⟨h, a^{−1}qhqa⟩ or L_{4} = ⟨h, a^{−1}qphpqa⟩. These subgroups all have index dividing 16 in G, and index dividing 8 in T = ⟨h, a^{−1}ha, p, q, r⟩, with transversal in T being a subset of the dihedral subgroup A = ⟨p, q, r⟩ of order 8. Since h^{−1}ph = q, h^{−1}qh = pq, h^{−1}pqh = p, it follows that if H contains one of the elements p, q and pq, then it contains all of them, and has therefore index at most 2 in T, a contradiction. Observe also that r^{−1}L_{1}r = L_{3} while r^{−1}L_{2}r = L_{4}.

In the case of G_{4}^{1}, the subgroup L_{1} is normalised by a, while L_{2}, L_{3} and L_{4} are normalised by ap, aqr and arq respectively. Hence the index of H in T has to be 4, and H must be of the form ⟨L_{i}, u⟩ where u is an element of A \ ⟨p, q⟩ = {r, pr, qr, pqr} normalizing L_{i}. It is easy to check, however, that this is impossible for all four subgroups L_{i}; for example, prhrp = ph^{−1}p = pqh^{−1} but pq ∉ H, and although rhr = h^{−1} we have also r(a^{−1}ha)r = ra^{−1}hqa = ra^{−1}pha = rpa^{−1}ha = p(a^{−1}ha) but p ∉ H.

In the case of G_{4}^{2}, observe that a^{−1}pL_{1}pa = ⟨a^{−1}phpa, a^{−1}pahapa⟩ = ⟨a^{−1}phpa, h⟩ = L_{2} since apa = a^{4} = p^{2} = 1, and hence that all four subgroups L_{1}, L_{2}, L_{3} and L_{4} are conjugate to L = L_{1} = ⟨h, a^{−1}ha⟩ in G. We can therefore assume without loss of generality that L ≤ H. Now consider the action of the group T on the right cosets of its subgroup L. The permutations induced by its generators h, a^{−1}ha, p, q and r are as follows:

• h induces the permutation (L)(Lp, Lq, Lpq)(Lpr, Lpqr, Lqr)(Lr);

• a^{−1}ha induces the permutation (L)(Lp, Lr, Lpr)(Lq)(Lpq, Lqr, Lpqr);

• p induces the permutation (L, Lp)(Lq, Lpq)(Lr, Lpr)(Lqr, Lpqr);

• q induces the permutation (L, Lq)(Lp, Lpq)(Lr, Lpqr)(Lpr, Lqr); and

• r induces the permutation (L, Lr)(Lp, Lpr)(Lq, Lqr)(Lpq, Lpqr).

These permutations generate a group of order 168 isomorphic to PSL(2,7) in its natural representation on the projective line over GF(7), as may be seen from the correspondence which takes (L, Lp, Lqr, Lpq, Lq, Lr, Lpr, Lpqr) to (∞, 0, 1, 2, 3, 4, 5, 6), and the permutations induced by the generators h, a^{−1}ha, p, q and r of T to the transformations z ↦ 2z + 1, z ↦ 2z − 1, z ↦ 3/z, z ↦ (z − 3)/(z − 1) and z ↦ (−z − 3)/(z + 1) respectively. In particular, as this permutation representation is primitive, we find that L ≤ H is a maximal subgroup of T, implying L = H, as required.

Finally, if G belongs to Djoković-Miller class G_{5}, then G_{v} ≅ S_{4} ×C_{2} is generated by h and four involutions p, q, r and s such that pq = qp, pr = rp, ps = sp, qr = rq, qs = sq, (rs)^{2} = pq, h^{−1}ph = p, h^{−1}qh = r, h^{−1}rh = pqr, shs = h^{−1}, ap = qa and ar = sa, and a itself is an involution. Again we find that G_{v} has eight elements of order 3, so aya^{−1} = h^{±1} or qh^{±1}q or rh^{±1}r or rqh^{±1}qr, and hence H contains at least one of M_{1} = ⟨h, a^{−1}ha⟩, M_{2} = ⟨h, a^{−1}qhqa⟩, M_{3} = ⟨h, a^{−1}rhra⟩ and M_{4} = ⟨h, a^{−1}rqhqra⟩. These subgroups all have index dividing 32 in G, and index dividing 16 in T, with transversal in T being a subset of the subgroup A = ⟨p, q, r, s⟩ ≅ D_{4} ×C_{2}. Also p^{−1}M_{1}p = M_{2} and s^{−1}M_{1}s = M_{3} and (ps)^{−1}M_{1}ps = M_{4}, so that all four subgroups are conjugate in T, and hence we may suppose that H contains M = M_{1} = ⟨h, a^{−1}ha⟩. Moreover, as M is normalised by a, we know H ≠ M and therefore H must contain at least one element of A = ⟨p, q, r, s⟩. But if H contains p, then H contains (a^{−1}ha)^{−1}p(a^{−1}ha) = s and (a^{−1}ha)p(a^{−1}ha)^{−1} = pqs, and therefore contains also p(pqs)s = q and h^{−1}qh = r, and so contains all of T, contradiction. Hence p ∉ H. A similar argument shows that H contains none of {p, q, r, s, pqr, pqs}. Furthermore, this shows prs ∉ H, for otherwise H would contain hprsh = phrh^{−1}s = pqs, and similarly qrs ∉ H. On the other hand, if H contains pq, then H contains also h^{−1}pqh = pr and (a^{−1}ha)pq(a^{−1}ha)^{−1} = ps, and therefore contains the subgroup ⟨h, a^{−1}ha, pq, pr, ps⟩, which has index 2 in T, contradiction. Hence pq ∉ H, and the same sort of argument shows that H contains none of {pq, pr, ps, qr, qs}. In particular, rs ∉ H (for otherwise pq = (rs)^{2} ∈ H), and similarly pqrs = sr ∉ H.

This completes the proof.

Theorem 5.2 Let X be a connected cubic bipartite edge-transitive graph with automorphism group G, and let S be a simple group other than ZZ_{3} such that S is normal in some semisymmetric group H ≤ G, and such that the quotient X_{S} is isomorphic to K_{1,3}. Then the following hold:

(i) N_{G}(H) ≤ N_{G}(S);

(ii) N_{G}(S) acts semisymmetrically on X;

(iii) N_{G}(S) is a self-normalising subgroup of G, that is, N_{G}(N_{G}(S)) = N_{G}(S);

(iv) X is semisymmetric.

Proof. Observe first that H acts transitively on both parts of the bipartition of X, and that S acts transitively on one part and intransitively (with three orbits of equal length) on the other part. This implies that

|H : S| = |H_{u} : S_{u}| = 3|H_{v} : S_{v}|  (∗)

where u is a vertex of the part on which S acts transitively and v is a vertex of the other part. In particular, by Goldshmidt’s theorem [20], the index |H : S| divides 3 · 2^{s−1} for some s ≤ 9. (Moreover, if X were symmetric, then we would have s ≤ 5 by the earlier theorem of Tutte [37]). Note also that since S is transitive on one part of the bipartition, and the cardinality of both parts is divisible by 3, the cardinality of S is divisible by 3, and |S| > 3.

Let us now prove part (i). Assume the contrary. Then there exists an element g ∈ G which normalises H but does not normalise S. It follows that the conjugate S^{g} is a normal subgroup of H^{g} = H, so also S ∩ S^{g} is a normal subgroup of S, and by simplicity of S, we find S ∩ S^{g} = 1. This implies that the normal subgroup SS^{g} of H is isomorphic to the direct product S × S, of order |S|^{2}. In particular, the index |H : S| is divisible by |S|, and so by (∗), |S| divides 3 · 2^{s−1}, and hence S ≅ ZZ_{2} or ZZ_{3}, contradicting the fact that |S| > 3. Thus N_{G}(H) ≤ N_{G}(S).

To prove parts (ii) and (iii), observe that S cannot be normal in any vertextransitive subgroup of G, since its actions on the two parts of the bipartition are not equivalent. In particular, N_{G}(S) is edge- but not vertex-transitive. But now applying part (i) to N_{G}(S) in place of H, we find N_{G}(N_{G}(S)) ≤ N_{G}(S), and thus N_{G}(S) is a self-normalising semisymmetric subgroup of G.

Finally, let us prove that the graph X is not vertex-transitive. Assume the contrary. As a consequence of part (ii) we can assume without loss of generality that N_{G}(H) = H. Hence by Proposition 5.1, the group H has a homomorphic image isomorphic to a point-stabiliser in the natural action of P SL(2, 7) on the projective line P G(1, 7). This is a group of order 21, and so H must have both the cyclic groups C_{3} and C_{7} among its composition factors. On the other hand, we know that H contains a nonabelian simple normal subgroup S of index dividing 3 · 2^{s−1} for some 1 ≤ s ≤ 5, and so C_{7} cannot be a composition factor of H. This contradiction completes the proof.

In what follows we construct some infinite families of connected cubic graphs, the semisymmetry of which follows from Theorem 5.2.

Construction 5.3 Let G be the direct product C × S, where C is a cyclic group generated by an element c of order 3, and S is a non-abelian simple group that can be generated by two elements a and b of order 3. Define P_{1} = ⟨ca⟩ and P_{2} = ⟨b⟩, and observe that the pair of inclusions (P_{1} → G, P_{2} → G) is a faithful finite completion of the amalgam (1 → P_{1}, 1 → P_{2}). Now take X to be the graph of this completion, with vertex-set the union G/P_{1} ∪ G/P_{2} of right cosets of P_{1} and P_{2} in G, and with two cosets P_{1}x and P_{2}y adjacent in X if and only if P_{1}x ∩ P_{2}y ≠ ∅. Observe also that G acts on X by right multiplication of cosets, and that this action is semisymmetric (of Goldschmidt type G_{1}). Moreover, the subgroup S acts transitively on the coset space (G : P_{1}) but has three orbits on (G : P_{2}). The corresponding quotient graph X_{S} is therefore isomorphic to K_{1,3}, and so by Theorem 5.2, the graph X is semisymmetric.

Note that graphs S120, S336b, S336c and S720b in our list can be obtained in this way. To illustrate its generality, we remark that many simple groups can be generated by two elements of order 3, and can thus be used in the above construction. Among these are all alternating groups A_{n} for n ≥ 3, all P SL_{2}(p) and P SL_{3}(p) for prime p, all P SL_{n}(q) and P SU_{n}(q) for large n and all prime powers q, many other families of simple groups of Lie type, and most of the sporadic simple groups, including the Monster. (Note that most of these groups can be generated by two elements x and y of orders 2 and 3, and then simplicity implies that these groups can also be generated by y and y^{x}.)

The next construction is a generalisation of 5.3.

Construction 5.4 Let (ϕ_{1} : B → P_{1}, ϕ_{2} : B → P_{2}) be a finite primitive amalgam of index (3, 3), such that for i = 1 or 2 (say i = 2), the image Im ϕ_{i} is normal in P_{i}. By Theorem 2.2 there are exactly four isomorphism classes of such amalgams, namely G_{1}, G_{1}^{2}, G_{2} and G_{2}^{3}. Further, let (ψ_{1} : P_{1} → S, ψ_{2} : P_{2} → S) be a faithful finite completion of the above amalgam, where S is a simple group. Without loss of generality we may assume that homomorphisms ϕ_{i} and ψ_{i} are inclusions (for i = 1 and 2), so that P_{1} and P_{2} are subgroups generating S, and B = P_{1} ∩ P_{2}. Note that by Proposition 2.1 this is equivalent to the following situation: S is a simple group acting semisymmetrically on a connected bipartite cubic graph, such that the intersection B of the stabilisers P_{1} and P_{2} of two adjacent vertices is normal in P_{2}.

Now let C be a cyclic group of order 3 generated by an element z, and let G be the direct product C × S. Since B is a normal 2-subgroup of index 3 in P_{2}, the group P_{2} is isomorphic to the semidirect product B ⋊ ⟨y⟩, where y^{3} = 1, and there exists a natural epimorphism π: P_{2} → ⟨y⟩ with kernel B. We can now define group homomorphisms

f_{1} : P_{1} → C × S by f_{1}(g) = (1, g), and f_{2} : P_{2} → C × S by f_{2}(g) = (π(g), g).

These homomorphisms are clearly injective, and the simplicity of S implies that their images generate C × S. Indeed, let H be the group generated by Im f_{1} and Im f_{2}. Since P_{1} and P_{2} generate S, the projection of H onto the second factor of C × S is S itself, and so H has index 1 or 3 in C × S. In the latter case, H would be isomorphic to S, and therefore simple. Also S ∩ H would be a normal subgroup of H of index 1 or 3, and since H is simple and |H| = |S| > 3, the index cannot be 3, so S ∩ H = H. This is impossible, however, because f_{2}(x) = (z, x) ∉ S. Thus H = G = C × S.

The above implies that the pair of homomorphisms (f_{1}, f_{2}) gives a finite faithful completion of the amalgam (ϕ_{1}, ϕ_{2}). Let X be the graph of this completion, with vertex-set (G : Im f_{1}) ∪ (G : Im f_{2}). By Proposition 2.1, the group G = C × S acts semisymmetrically on X. Observe also that its subgroup S acts transitively on (G : Im f_{2}), but has three orbits on (G : Im f_{1}). The quotient graph X_{S} is therefore isomorphic to K_{1,3}, and by Theorem 5.2, X is semisymmetric.

This construction may be used to obtain the graphs S330, S546b and S660 in our list. (Also Construction 5.3 can be obtained as a special case of this one, by choosing the amalgam (ϕ_{1}, ϕ_{2}) to be of type G_{1}.)

The following proposition introduces a third construction, for producing a connected bipartite cubic graph that admits a semisymmetric action of a semidirect product of a simple group by a cyclic group of order 3.

Proposition 5.5 Let S be a simple group which has an automorphism ω of order 3, and let B and P be proper subgroups of S such that:

(i) B is a subgroup of P of index 3, and B is either trivial or not normal in P;

(ii) B^{ω} = B;

(iii) The subgroup generated by P, P^{ω} and P^{ω^{2}} is S.

Further, let G be the semi-direct product S ⋊ ⟨ω⟩, and define P_{1} = P (viewed as a subgroup of G) and P_{2} = ⟨B, ω⟩, the subgroup of G generated by B and ω (isomorphic to the semi-direct product B ⋊ ⟨ω⟩). Then:

(a) B = P_{1} ∩ P_{2}, and the pair of inclusions (ϕ_{1} : B → P_{1}, ϕ_{2} : B → P_{2}) is a primitive amalgam of index (3, 3); (b) the pair of inclusions (ψ_{1} : P_{1} → G, ψ_{2} : P_{2} → G) is a faithful finite completion

of the amalgam (ϕ_{1}, ϕ_{2});

(c) the graph X of this completion admits a semisymmetric action of G, such that the quotient graph X_{S} is isomorphic to K_{1,3};

(d) X is a connected semisymmetric cubic graph.

Proof. Everything in part (a) is obvious except for the fact that the amalgam (ϕ_{1}, ϕ_{2}) is primitive. So let us assume that (ϕ_{1}, ϕ_{2}) is not primitive. Then there exists a non-trivial subgroup K of B such that either:

• K is normal in P_{1} and the normaliser N_{P_{2}}(K) properly contains B, or

• K is normal in P_{2} and the normaliser N_{P_{1}}(K) properly contains B.

In the former case N_{P_{2}}(K) = P_{2}, since B is maximal in P_{2}, and so ω ∈ P_{2} normalises K and therefore K is normal in ⟨P_{1}, P_{1}^{ω}, P_{1}^{ω^{2}}⟩ = S, but that is impossible since S is simple. In the latter case N_{P_{1}}(K) = P_{1} since B is maximal in P_{1}, while ω normalises K because ω ∈ P_{2}, and again K is normal in ⟨P_{1}, P_{1}^{ω}, P_{1}^{ω^{2}}⟩ = S, which is impossible because S is simple.

To prove part (b) we need only show that P_{1} and P_{2} generate G. This follows directly from the fact that ⟨P, P^{ω}, P^{ω^{2}}⟩ = S implies G = ⟨S, ω⟩ = ⟨P, ω⟩ = ⟨P_{1}, P_{2}⟩.

For part (c), recall that the two parts of the bipartition of X consist of right cosets of P_{1} and P_{2} in G, respectively, and that G acts as a group of automorphisms of X by right multiplication. Clearly S ≤ G acts transitively on the cosets of P_{2} = ⟨ω⟩B in G = ⟨ω⟩S, in essentially the same way as S acts on the cosets of B. On the other hand, S acts intransitively on the cosets of P_{1} = P in G, with three orbits corresponding to the cosets S, ωS and ω^{2}S. The quotient graph X_{S} is thus indeed isomorphic to K_{1,3}.

Finally, part (d) follows immediately from Theorem 5.2.

Example 5.6 Let F = GF (2^{3}) be the finite field with 8 elements, let λ be the generator of the multiplicative group F^{∗} satisfying λ^{3} + λ + 1 = 0, and let

b = [ \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ] and a = [ \begin{matrix}λ & λ^{−1} \\ λ^{−1} & λ^{3} \end{matrix} ]

be two elements of S = SL(2, F) ≅ P SL(2, 8). Also let B = ⟨b⟩ and P = ⟨B, a⟩. Note that P is a subgroup of S isomorphic to S_{3}. Next let ω be the automorphism of F mapping λ to λ^{2}, which has order 3 since λ^{ω^{3}} = λ^{8} = λ. It is easy to check that ⟨a, a^{ω}, a^{ω^{2}}⟩ = S, so all conditions of Proposition 5.5 are satisfied. The resulting graph X is a connected semisymmetric cubic graph on 504 vertices, isomorphic to the graph S504 in our list.

Example 5.7 Let S, a and ω be as in the previous example, but let B be the trivial subgroup of S, and P = ⟨a⟩. Then the conditions of Proposition 5.5 are again satisfied, and the resulting graph is a connected semisymmetric cubic graph on 1008 vertices.

6 The diagrams — explaining the list

In this section we explain some of the structure and number of aspects of the list of semisymmetric graphs provided in Section 7. To do this, we need to discuss relationships between members of a class of graphs, as follows.

Irreducible morphisms and direct objects Let C be a class of graphs and graph morphisms (not necessarily a subcategory of graphs). A graph in C is called basic if it has no morphism in C to another graph in C. A morphism X → Y in C is irreducible if it cannot be written as a composition of two morphisms (neither being an isomorphism) in C. A graph X is a direct object over a graph Y if the set Hom_{C}(X, Y) ≠ ∅ consists of irreducible morphisms only (which are then called direct morphims). For example, in the context of all graphs and regular covering projections, ℘: X → Y is irreducible if and only if CT(℘) is a simple group; in addition, if CT(℘) is abelian then X is a direct object over Y, but might fail to be direct if CT(℘) is nonabelian. (We remark that in this setting the concept of a direct object corresponds to that of a direct cover as defined in the Foster census [4].)

When restricting to a specific subclass of graphs (and/or specific regular covering projections), the characterisation of irreducible morphisms, let alone direct ones, largely depends on the chosen subclass — as taking a quotient by the action of a semiregular group may result in a graph (and/or a morphism) outside that subclass; on one hand, some of the irreducible morphisms might not be included in the class at all, and on the other hand, a previously reducible projection might become irreducible. For instance, within the class of cubic arc-transitive graphs and regular covering projections there exist irreducible morphisms, even direct ones such as F8 → F2, with a nonsimple group as the group of covering transformations.

When speaking of cubic semisymmetric graphs it is necessary to consider all cubic edge-transitive graphs as objects and a certain subclass of regular covering projections as morphisms. This needs further explanation. First, note that there are semisymmetric cubic graphs which have a regular covering projection onto a smaller cubic arc-transitive graph (for example, the smallest one, the Gray graph S54, has a projection onto the Pappus graph F18). Second, as for the choice of morphisms we have restricted ourselves to consider only edge-transitive regular covering projections. By definition, a regular covering projection ℘_{N}: X → X_{N} is edge-transitive if at least one (minimal) edge-transitive subgroup of Aut X projects along ℘_{N} (implying that both graphs in question must be edge-transitive). By Proposition 3.1, ℘_{N} is edge transitive if and only if N is normalized by some (minimal) edge-transitive subgroup of Aut X; this is equivalent to requiring that N is normal in some edge-transitive subgroup of Aut X or, that the normalizer of N within Aut X is edge-transitive. In view of the above morphism restrictions it follows that an edge-transitive graph is basic whenever it has no edge-transitive covering projection onto a smaller edge-transitive graph, that is, if and only if no edge-transitive subgroup of Aut X has a semiregular normal subgroup.

Note that each edge-transitive graph is a quotient graph arising from an edgetransitive covering projection (for instance, by taking an appropriate voltage assignment with values in the first homology group of the graph, the respective covering projection is edge-transitive). Therefore by restricting ourselves to edge-transitive covering projections, no basic graph (in the wider context of all regular covering projections) is lost; the set of basic graphs could just be larger. (No example is known to the authors, however, of a cubic edge-transitive graph covering another cubic edge-transitive graph with no covering projection between them being edge-transitive.)

Finally, we remark that in a later subsection we shall extend our class of morphisms to include all edge-transitive quotient projections.

Excluding strongly reducible morphisms Clearly we would like to omit redundant morphisms (ideally, we would keep just the direct ones, up to isomorphism of projections) and even the unnecessary arc-transitive graphs, and still be able to generate all semisymmetric graphs starting from the set of basic graphs (by reconstructing each of the remaining covering projections in terms of voltages).

Recall that an edge-transitive regular covering projection ℘_{N}: X → X_{N} is reducible if there exists a decompostion ℘_{N} = ℘_{N/K} ∘℘_{K} where ℘_{K} and ℘_{N/K} are edge-transitive. In particular, ℘_{N} is strongly reducible whenever there exists K ◁ N such that some edge-transitive subgroup projects simultaneously along ℘_{N} and ℘_{K}. Unfortunately, reducible projections which are not strongly reducible may exist.

Lemma 6.1 An edge-transitive regular covering projection ℘_{N}: X → X_{N} is strongly reducible if and only if there exists an edge-transitive group H ≤ Aut X such that N is normal but not a minimal normal subgroup of H.

By Lemma 6.1, it suffices to consider all edge-transitive subgroups H ≤ Aut X and then take quotients by the action of all subgroups in H which are minimal with respect to being normal and semiregular on X. Since each subgroup of a semiregular group is semiregular, these minimal subgroups are minimal normal subgroups of H which are, in addition, semiregular on X. Moreover, we can consider edge-transitive subgroups and their minimal normal subgroups only up to conjugation in Aut X. Namely, normality and semiregularity are preserved under conjugation, and the projection relative to conjugate subgroups results in isomorphic covering projections. Now, if a selected subgroup N is normal and not minimal normal in some other edge-transitive subgroup (where “some other” should be understood as relative to all edge-transitive subgroups, not just subgroups up to conjugation), then such a projection is discarded. Repeating the procedure recursively on all graphs thus obtained, no “smaller object below X” is lost, and all morphisms are either irreducible, or at least not strongly reducible.

Strong reducibility can also be studied in terms of lifting edge-transitive subgroups along ℘: Y → X (usually given by means of a voltage assignment on X). Observe that if ℘: Y → X is a regular covering projection and if some (minimal) edge-transitive subgroup of G ≤ Aut X lifts, then the lift G̃ ≤ Aut Y is edge-transitive and hence ℘ is edge-transitive. The next lemma says that ℘ is strongly reducible if and only if there exists a decomposition ℘ = ℘_{N} = ℘_{N/K} ∘℘_{K} and a (minimal) edge-transitive subgroup of Aut X which lifts both along ℘_{N} and ℘_{N/K}.

Lemma 6.2 An edge-transitive regular covering projection ℘: Y → X is strongly reducible if and only if there exists a minimal edge-transitive subgroup G ≤ Aut X such that ℘ is G-admissible but not minimally G-admissible.

In view of Lemma 6.2, it suffices to consider all minimal edge-transitive subgroups G ≤ Aut X, and then find all minimally G-admissible covers of X (up to isomorphism of covering projections). Moreover, we can consider minimal edge-transitive subgroups only up to conjugation in Aut X. Namely, if G ≤ Aut X lifts along ℘_{ζ}: Cov(X; ζ) → X then a conjugate subgroup G^{α} lifts along an isomorphic covering projection ζ^{α}, defined by ζ^{α}(a) = ζ(α^{−1}(a)) for each arc a ∈ A(X). (Note that G^{α} might not lift along ℘_{ζ}.) Repeating the procedure recursively on all larger graphs thus obtained, no “object above X” is lost. (If there is an edge-transitive graph which covers X but does not cover X edge-transitively, then such a graph is basic and needs to be found by other means.) All morphisms constructed this way are either irreducible, or at least not strongly reducible.

Characterising irreducible morphisms Let ℘_{N}: X → X_{N} be a reducible but not strongly reducible edge-transitive regular covering projection, and let ℘_{N} = ℘_{N/K} ∘℘_{K} be an edge-transitive depomposition. In such a case, edge-transitive subgroups of Aut X_{K} projecting along ℘_{N/K} are not related to edge-transitive-subgroups of Aut X (via their projections along ℘_{K}). Similarly, no lift along ℘_{N/K} of any edge-transitive group lifts along ℘_{K}. This makes the characterisation of irreducible morphisms rather difficult if not impossible.

We discuss the matter in some detail from the point of view of projecting groups first. Let N_{min} = ∪Min_{◁}H be the set of all minimal normal subgroups of all edgetransitive subgroups H ≤ Aut X, and let nInc denote the “normal subgroup” relation. Observe that the set of nInc-minimal elements

M = minnInc ⋃ ; H edge-transitive Min_{◁}H

can also be described as the set of all nInc-minimal elements in the set of all subgroups of Aut X which are normalized by some minimal edge-transitive group, that is,

M = minnInc{M | M is normalized by a minimal edge-transitive subgroup}.

After calculation of the nInc-minimal elements, the set M can be reduced up to conjugation — but not before. Now, if N ∈ M acts semiregularly on the graph, then ℘_{N} is edge-transitive and irreducible. However, the set

minnInc {N_{min} \ M}

may contain groups, acting semiregularly on X, which do not give rise to a strongly reducible projection. To decide whether such a projection ℘_{N} is reducible or not, one has to consider K ◁ N, K ∈ M and the quotient graph X_{K}. Therefore, by restricting just to groups in M, the reduction has gone too far. This can happen even in such special cases where Aut X has a single conjugacy class of minimal edge-transitive subgroups.

Specialising further we now consider the case where Aut X has a unique minimal edge-transitive subgroup (which is necessarily normal in Aut X). In such a case, an edge-transitive regular covering projection is either irreducible or strongly reducible, implying that irreducible projections can be characterised.

Lemma 6.3 Let X be an edge-transitive graph such that Aut X has a unique minimal edge-transitive subgroup, H. Let M be the set of all nInc-minimal elements

M = minnInc{M | M normalized by H} = minnInc ⋃ Min_{◁}H′, where the union is taken over all subgroups H′ of Aut X containing H. Then the quotient projection by a group N ≤ Aut X is an irreducible edge-transitive regular covering projection if and only if N is semiregular on X and N ∈ M.

Note that, in contrast with the general case, M now does contain all minimal normal subgroups of H (if H is not simple). The remaining groups in M, if any, must intersect H trivially.

As from the point of view of lifting groups we consider only the most particular case when Aut X has a unique minimal edge-transitive subgroup, H. Like above, an edge-transitive regular covering projection ℘: Y → X is now either irreducible or strongly reducible. Hence ℘ is irreducible if and only if it is minimally H-admissible, by Lemma 6.2.

Our reduced list of direct covers Returning to our list, a further removal of many arc-transitive graphs can be accomplished: if a graph X is arc-transitive, we keep only those graphs below X obtained by direct morphisms as found in the Foster census [4] (such morphisms are indeed edge-transitive). Moreover, there should be a semisymmetric cubic graph Y on up to 768 vertices and an edge-transitive regular covering projection Y → X.

As for the semisymmetric ones, recall that all such graphs in the list have been computed separately by other methods (so that we do have all the objects on up to 768 vertices). Checking their automorphism groups (using Magma [1]) reveals that, save for one single exception — the Gray graph — all have a unique minimal edgetransitive group which is, moreover, of index 1, 2, or 4 in the full automorphism group. As for the Gray graph, its minimal edge-transitive subgroups are precisely the Sylow 3-subgroups of its full automorphism group, and are thus pairwise conjugate.

The graphs F2, F4, F10, F28, F56b, F110, F182d, S110, S126, S182, S210, S504, S506 and S650 are basic, for they share the following property: no edgetransitive subgroup of the respective automorphism groups has a normal semiregular subgroup. This clearly holds for the arc-transitive ones, in view of the Foster census [4]. The minimal edge-transitive subgroup of S504 is its full automorphism group itself, isomorphic to PSL(2, 8) ⋊ ZZ_{3}, and PSL(2, 8) is its only proper nontrivial normal subgroup which is not semiregular since the respective quotient graph is K_{1,3}. The unique minimal edge-transitive subgroup H for each of the remaining graphs X is simple and of index at most 2 in Aut X. Therefore, a normal subgroup N ◁ Aut X either contains H or intersects H trivially. In the first case, N is edge-transitive and hence not semiregular on X. In the second case, N must be isomorphic to ZZ_{2}. However, all these graphs are of the form twice an odd number, and so quotienting by ZZ_{2} cannot result in a cubic graph.

As for the irreducible morphisms, in the case of Gray graph we can take just the quotient by the minimal normal subgroup, isomorphic to ZZ_{3}, of some Sylow 3subgroup. Namely, since the Gray graph has order 54 = 2 · 3^{3} and since cubic graphs have even order, the group by which we take the quotient must be a 3-group, and hence contained in a minimal edge-transitive subgroup. The respective covering projection is S54 → F18. All other irreducible morphisms are found using Lemma 6.3.

There are a few cases where N ∈ M intersects H trivially. In this case N must be a minimal normal subgroup of Aut X and isomorphic to ZZ_{2}. At most three such subgroups exist. This holds true because H is normal and of index 1, 2 or 4 in AutX.

The only remaining possiblity that N ≅ ZZ_{2}^{2} cannot occur for the following reason. If N ≅ ZZ_{2}^{2} then |Aut X : H| = 4 and N is a minimal normal subgroup of Aut X. But there is always a subgroup H′ ≤ Aut X of index 2 containing H, and N ∩ H′ must be a proper and nontrivial subgroup of N. So N ∩ H′ ◁ Aut X, a contradiction to the minimality of N. Thus, N ≅ ZZ_{2} is the only possibility. Clearly, N is the only subgroup of order 2 complementary to H in the group N × H (a subgroup of index 2 in Aut X). Hence N is also normal in Aut X. As there are at most three subgroups of index 2 containing H, there are at most three minimal normal subgroups of Aut X isomorphic to ZZ_{2} and having trivial intersection with H. However, a close inspection of our list shows that we only have cases where H is of index 2 and H is a simple group. Hence N is always unique. These are the cases S220 → F110, S364 → F182d and S420 → S210. In all other cases, the group N ∈ M is actually a minimal normal subgroup of H. There are never more than two such subgroups, and with a few exceptions, they are of coprime orders. Apart from S294 → S42, the minimal normal subgroups of H are always normal in Aut X.

Having found all irreducible morphisms, all graphs in the list can be constructed by a sequence of irreducible covering projections starting from the basic ones. Each semisymmetric graph projects onto at most two distinct smaller graphs in the list, and there are no nonisomorphic projections between the same pair of graphs in the list. Note that any composition of two or more irreducible morphisms is either a strongly reducible edge-transitive regular covering projection — or a covering projection which is not of our concern: a regular but not edge-transitive, or a nonregular covering projection.

We now show that all covering projections constructed as described above are actually direct. By the opening remarks at the beginning of this subsection, all morphisms between arc-transitive graphs are direct. This trivially holds also in all cases where the group of covering transformations is of prime order. So what we need to check are the following projections — those with |Aut X : H| = 1 (namely S112 → F14, S336a → F42, S400 → F16, S448 → F56a, S448 → S112, and S702a → F26), and those with |Aut X : H| = 2 (namely S144 → F16, S216 → S54, S432b → F48, S576 → F64, S576 → S144, and S768a → F192c), and finally, those with |Aut X : H| = 4 (namely S384 → F96b and S768b → F192a). All these covering projections arise as factorisations by a minimal normal subgroup of H.

If one of the above irreducible morphisms X → X_{N} is not direct, then there exists a subgroup N′ ≤ Aut X, acting semiregularly on X, such that N′ (together with one of its normal subgroups) is normalized by H and X_{N′} ≅ X_{N}. In particular, |N′| = |N|.

Now, if any two minimal normal subgroups of H have either equal or coprime cardinality, then N′ ∩ H = 1. So if |Aut X : H| ≤ 2, then N′ is either trivial or isomorphic with ZZ_{2}, a contradiction since ℘_{N′} was assumed strongly reducible. This allows us to dispose of the cases with |Aut X : H| = 1, except possibly for the projections S448 → F56a and S448 → S112, and of the cases with |Aut X : H| = 2, except possibly for the projections S432b → F48 and S768a → F192c. We now consider these four projections separately.

The minimal normal subgroups of H = Aut S448 are N_{1} ≅ ZZ_{2}^{3} and N_{2} ≅ ZZ_{2}^{2}, giving rise to the two irreducible projections in the list. Clearly, no projection ℘_{N′}: S448 → S112 is strongly reducible, for otherwise H would contain a minimal normal subgroup isomorphic to ZZ_{2}. So ℘_{N_{2}} : S448 → S112 is direct.

Suppose that ℘_{N′}: S448 → F56a is strongly reducible. As N′ is of order 8 and is not minimal normal in H = Aut S448, it contains N_{2}. Thus, ℘_{N′} would factorise via ℘_{N_{2}}. But this is not possible because Aut S112 (the minimal edge-transitive group of S112) does not have a normal subgroup isomorphic to ZZ_{2} (as in fact its minimal normal subgroup is ZZ_{2}^{3}). Consequently, ℘_{N_{1}} : S448 → F56a is direct.

Consider a strongly reducible projection ℘_{N′}: S432b → F48. The group N′ is of order 9, and since |Aut X : H| = 2, the group N′ is contained in H and is not minimal normal in H. The minimal normal subgroups of H are N_{1} ≅ ZZ_{3} and N_{2} ≅ ZZ_{3}^{2}. Thus N′ contains N_{1} ≅ ZZ_{3}, the group giving rise to the projection S432b → S144. The quotient group N′/N_{1} ≅ ZZ_{3} must be normalized by the minimal edge-transitive subgroup of Aut S144. But this minimal subgroup is also of index 2 in Aut S144, and must therefore contain the projection N′/N_{1}. However, the minimal edge-transitive subgroup of Aut S144 has only one minimal normal subgroup, and this is isomorphic to ZZ_{3}^{2}. Therefore, ℘_{N_{2}} : S432b → F48 is direct.

Consider a strongly reducible projection ℘_{N′}: S768a → F192c. The minimal normal subgroups of H are N_{1} ≅ ZZ_{2} and N_{2} ≅ ZZ_{2}^{2}. As |N′| = 4 and |Aut X : H| = 2, the group N′ has a nontrivial intersection with H, implying that ℘_{N′} factorises through ℘_{N_{1}} : S768a → S384. Thus Aut S384 has a group N′/N_{1} ≅ ZZ_{2} which is normalized by the minimal edge-transitive subgroup H′ ≤ Aut S384. The group N′/N_{1} is not contained in H′ since the minimal normal subgroup of H′ is isomorphic to ZZ_{2}^{2}. But neither can N′/N_{1} have trivial intersection with H′ for the following reason. First note that H′ has index 4 in Aut S384, and that there would be a group ZZ_{2} × H′ of index 2 in Aut S384 with a nontrivial centre. However, any of the three index 2 subgroups of Aut S384 are, according to Magma, centreless. This contradiction proves that ℘_{N_{2}} : S768a → F192c is direct.

To complete the proof we need to discuss the two cases where H is of index 4 in Aut X. First we consider a strongly reducible projection ℘_{N′}: S384 → F96b. Now, if N′ ∩ H = 1 then Aut S384 = N′ × H, and the centre of Aut S384 would be nontrivial. That is a contradiction, by Magma. We cannot have N′ ∩ H ≅ ZZ_{2} since the minimal normal subgroup of H is N = ZZ_{2}^{2}, and N′ ≤ H implies N′ = N, a contradiction. Thus, ℘_{N}: S384 → F96b is direct.

Finally, consider a strongly reducible projection ℘_{N′}: S768b → F192a. If N′ ∩ H = 1, then Aut S768b = N′ × H, a contradiction since the centre of Aut S768b coincides with that of H, by Magma. Now N′ ∩ H ≠ 1 implies that ℘_{N′} factorises through ℘_{N_{1}} : S768b → S384. But this would mean that the minimal edge-transitive subgroup of Aut S384 would normalize N′/N_{1} ≅ ZZ_{2}, a contradiction since S384 has a unique irreducible projection, the one by the action of ZZ_{2}^{2}. So ℘_{N_{2}} : S768b → F192a is direct.

The above discussion is summarised in the following theorem.

Theorem 6.4 Our list displays, up to isomorphism of covering projections, all possible constructions of all cubic semisymmetric graphs on up to to 768 vertices by taking successive direct regular covers of the following basic edge-transitive graphs: F2, F4, F10, F28, F56b, F110, F182d, S110, S126, S182, S210, S504, S506 and S650.

As was shown in [29], every finite cubic graph admitting an edge-transitive solvable group may be obtained from either the 3-dipole Dip_{3} (the graph F2), or the complete graph K_{4} (the graph F4), by a sequence of elementary abelian covers. In other words, F2 and F4 are the only basic graphs needed to generate all finite edge-transitive cubic graphs having a solvable automorphism group. Thus each of the 21 cubic semisymmetric graphs in our list that has a solvable automorphism group can be obtained from one of these two graphs, as may be seen from our first diagram, see Figure 5.

Figure 5.

The remaining 22 semisymmetric cubic graphs with a non-solvable automorphism group are displayed in Figures 6a and 6b. Note that every graph which reduces to F6 (the complete bipartite graph K_{3,3}) reduces also to K_{1,3}, see Figure 5. In Figures 6a and 6b, the eight irreducible quotients of semisymmetric graphs onto K_{1,3} are also displayed. These quotients are discussed below.

Figure 6a.

Figure 6b.

Quotients onto K_{1,3} There are several examples of cubic semisymmetric graphs in our list having the tripod K_{1,3} as a quotient, and as Section 5 demonstrates, they appear to be of particular interest. So let us enlarge our set of morphisms (and consequently, our set of objects). By definition, a quotient projection q_{N}: X → X_{N} is edge-transitive whenever at least one (minimal) edge-transitive subgroup of Aut X projects along q_{N}. By Proposition 3.1, q_{N} is edge-transitive if and only if Ker q_{N} is normalized by some (minimal) edge-transitive subgroup of Aut X.

As for the objects of our study, we note the following. If N is edge-transitive, then the quotient graph is obviously isomorphic either to K_{2} or to a one-vertex graph with a single loop or semiedge. Such quotients appear worthless and are exluded from further consideration. If N is not edge-transitive then an edge-transitive quotient projection is either a regular covering projection, or else X is bipartite and X_{N} ≅ K_{1,3}. In view of these remarks, our extended class C of graphs and morphisms now includes: all edgetransitive cubic graphs as well as the graph K_{1,3} as objects, and all edge-transitive regular covering projections together with all edge-transitive quotient projections onto K_{1,3} as morphisms. The set of basic graphs consists of the graph K_{1,3} and of all cubic edge-transitive graphs, which are basic relative to edge-transitive regular covering projections and do not have an edge-transitive quotient projection onto K_{1,3}. However, we still prefer to view all graphs that are basic in the old sense, as basic. (In the list on up to 768 vertices only the graph S504 is, formally, not basic anymore.)

When discussing (ir)reducibility of morphisms, the situation with non-covering quotient projections is subtler and more difficult to analyse because of certain anomalies which never occur with regular covering projections. In particular, a reducible quotient projection q_{N}: X → X_{N} might not arise as a strong decomposition. This anomaly can occur even if q_{N} is strongly reducible (that is, one can have a decomposition q_{N} = q_{M} ∘ q_{K} where an edge transitive subgroup H ≤ Aut X projects along q_{N} and along q_{K} — and hence H̄ = q_{K}^{∗}(H) projects along q_{M} — however N does not project along q_{K}). In our case the analysis is simplified to some extent — partly because noncovering quotients involve just a single graph, K_{1,3}, and partly because each semisymmetric graph X on up to 768 vertices has a single minimal edge-transitive group (save for the Gray graph). But even this does not seem to be enough to obtain a characterisation of irreducible morphisms comparable to that of Lemma 6.3 (and worse, not even a characterisation of strongly reducible morphisms as in Lemma 6.1). The crucial additional information used in the analysis below is the fact that the minimal edge-transitive subgroup has a very small index in Aut X. Thus, we do not attempt to give a general approach to this problem (not even in the case of cubic graphs), and the special case of the Gray graph is treated separately.

Recall that the Gray graph has four minimal edge-transitive groups, namely the four Sylow 3-subgroups of order 81 (thus acting regularly on the set of edges) having index 16 in the full automorphism group. Let N be a subgroup giving rise to an edge-transitive quotient onto K_{1,3}. Then, as N acts transitively on one bipartition set of 27 vertices, |N| is divisible by 27. Now, a Sylow 3-subgroup of N is entirely contained in some Sylow 3-subgroup H of the full automorphism group, and must have order at least 27. So the Sylow 3-subgroup of N is precisely H ∩ N. As N ≠ H we have that |H ∩ N| = 27. Moreover, since H ∩ Ker q_{N} cannot be H, we have H ∩ N = H ∩ Ker q_{N}. Thus, H ∩ N is normal in H. The group H ∩ N cannot give rise to a covering projection for the respective quotient would be the dipole F2 (which does not have a graph morphism onto K_{1,3}). Consequently, quotienting by H ∩ N gives us K_{1,3}, and q_{H∩N} = q_{N}. Now H has a unique minimal normal subgroup N_{0} ≅ ZZ_{3} (contained in H ∩ N) which gives rise to a regular covering projection onto F18. So q_{N} = q_{H∩N/N_{0}} ∘ q_{N_{0}} is an edge-transitive strong decomposition. Thus, no edge-transitive quotient of the Gray graph onto K_{1,3} is irreducible.

Lemma 6.5 Let X be an edge-transitive cubic graph having a unique minimal edgetransitive subgroup H ≤ Aut X of index 1, 2 or 4 in Aut X. If q_{N}: X → K_{1,3} is an irreducible edge-transitive quotient projection, then q_{N} = q_{N_{0}}, where N_{0} is a minimal normal subgroup of H.

Proof. First observe that N ∩ H is nontrivial. For otherwise N is a group of order at most 4 and hence |V (X)| ≤ 2|N| ≤ 8 (the first inequality follows from the fact that N acts transitively on one part of the bipartition set of X). So X is either F8 or K_{3,3}. Now, although F8 and K_{3,3} do have K_{1,3} as an epimorphic image, neither can be realised as an edge-transitive quotient by a subgroup outside the minimal edgetransitive group. Thus, N ∩ H is indeed nontrivial. Consider N′ = Ker q_{N} ∩ H. As H normalizes Ker q_{N} we have N′ ◁ H. Also, N′ is normal in Ker q_{N} (because H is normal in Aut X) and hence N normalizes N′. Therefore, there exists a strong edgetransitive decomposition q_{N} = q_{N/N∩N′} ∘ q_{N′}. But q_{N} is assumed irreducible, implying that q_{N′} = q_{N}. Now let N_{0} be a minimal normal subgroup of H contained in N′. Then q_{N} = q_{N′} = q_{N′/N_{0}} ∘ q_{N_{0}} is an edge-transitive strong decomposition. Since q_{N} is assumed irreducible, the decomposition is trivial. Therefore, q_{N} = q_{N_{0}}.

There are eight semisymmetric graphs in our list having an edge-transitive quotient projection onto K_{1,3} arising from a minimal normal subgroup N of H; namely, the following: S120, S330, S336b, S336c, S504, S546b, S660 and S720b. Moreover, N is uniquely determined since in all cases H = ZZ_{3} × N. Thus, N is always normal in Aut X.

Note that if N is a minimal normal subgroup of H giving a quotient onto K_{1,3}, then q_{N} might still be reducible (but it is unclear whether such a case exists or not). This is in striking contrast with the situation encountered in Lemma 6.3. Fortunately, nothing like that happens in the case of our finite list.

Lemma 6.6 Let X be an edge-transitive cubic graph having a unique minimal edgetransitive subgroup H ≤ Aut X of index 1, 2 or 4 in Aut X, and let N be a minimal normal subgroup of index 3 in H giving rise to an edge-transitive quotient projection q_{N}: X → K_{1,3}. If q_{N} is reducible, then there exists a strong edge-transitive decomposition q_{N} = q_{N/N∩L} ∘ q_{L}, where L ≅ ZZ_{2} intersects H trivially.

Proof. Let K = Ker q_{K} be a nontrivial semiregular subgroup contained in Ker q_{N} giving rise to an edge-transitive decomposition of q_{N}. Consider N′ = Ker q_{N} ∩ H ◁ H. Since N ≤ N′ ≤ Ker q_{N} we have q_{N′} = q_{N} (and N′ is actually the largest subgroup of H with this property). Thus, N′ ≠ H. So |H : N| = 3 implies N′ = N. It follows that H ∩ K ≤ H ∩ Ker q_{N} = N, and since K is normalized by H we have H ∩ K ◁ H. But N is a minimal normal subgroup of H. As H ∩ K is also semiregular on X and hence not equal to N, we have H ∩ K = 1. Consequently, K is a group of order 2 or 4. Now, if H = Aut X then K = 1, a contradiction. If |Aut X : H| = 2, let L = K ≅ ZZ_{2}. If |Aut X : H| = 4 then since H is normal in Aut X, there is always a subgroup H′ of index 2 in Aut X which contains H as an index 2 subgroup. In this case, let L = K ∩ H′ ≅ ZZ_{2}. In both cases the group L is normalized by H, and in particular, by N. So we do have an edge-transitive strong decomposition q_{N} = q_{N/N∩L} ∘ q_{L}.

This lemma guarantees that, in our finite list, all quotients of semisymmetric graphs onto K_{1,3} arising from minimal normal subgroups of H are indeed irreducible. Namely, the only cases where there exists an edge-transitive regular covering projection by the action of a group ZZ_{2} intersecting the minimal edge-transitive subgroup trivially, are the cases S220 → F110, S364 → F182d and S420 → S210. But in all these three cases the minimal edge-transitive subgroup is simple. Hence the respective graphs cannot have an edge-transitive quotient onto K_{1,3}.

There are other quotients onto K_{1,3} in the list which are reducible. We now show that these cannot be defined on the semisymmetric graphs listed above, that is, all irreducible quotients in the list are indeed direct. So let q_{N_{0}} : X → K_{1,3} be an irreducible quotient projection, where N_{0} is a minimal normal subgroup of index 3 in the minimal edge-transitive subgroup H of Aut X. Further, let q_{N}: X → K_{1,3} be reducible. Consider N′ = Ker q_{N} ∩ H which must be normal in H. If N_{0} ≤ N′ then q_{N} = q_{N_{0}}, a contradiction since q_{N} is assumed reducible while q_{N_{0}} is not. So N′ ∩ N = 1, implying that N′ ≅ ZZ_{3}. Hence X is isomorphic to K_{3,3}, a contradiction.

The preceeding discussion is summarised in the following theorem.

Theorem 6.7 In our finite list, each semisymmetric graph having an irreducible edgetransitive quotient projection onto K_{1,3} is a direct object over K_{1,3}.

7 The list

We are now ready to display the list of all connected cubic semisymmetric graphs on up to 768 vertices. For each graph in the list we have computed the order of the minimal edge-transitive group H. Recall that, except in the case of the Gray graph, this group is unique and characteristic in the full automorphism group. We have also computed (up to isomorphism of quotient/covering projections) all its direct quotient and covering projections. As explained in Section 6, these are found by taking the quotient relative to minimal normal subgroups of H (also in the case of the Gray graph), except for the three cases where the quotient is taken by an action of ZZ_{2} outside H. For each projection we found the respective quotient graph, and the largest subgroup of the full automorphism group that projects. The use of Magma [1], and to some extent also the ATLAS [9], proved to be very helpful in our computations.

In summary the following information on these graphs is given in the list:

(i) the order;

(ii) the diameter;

(iii) the girth;

(iv) the order of the full automorphism group, as well as the order of the corresponding vertex stabilisers;

(v) the Goldschmidt type, together with additional relations which are satisfied by the generators of the automorphism group;

(vi) the two distance partitions with their refinements into orbits of the corresponding vertex stabilisers;

(vii) the order of a minimal edge-transitive subgroup (denoted by mET) with some additional information such as its solvability, simplicity, and isomorphism class;

(viii) all of its direct covers in the list, and the corresponding indices of the minimal edge-transitive subgroup in the maximal group that lifts;

(ix) all of its direct quotients (including the arc-transitive ones) and the maximal group that projects;

(x) possible membership of one of the families described in Section 7;

(xi) information on whether the graph is a basic semisymmetric graph, that is, a graph having no smaller regular graph as an edge-transitive quotient;

(xii) additional group relations which give, together with the Goldschmidt type, full information on the automorphism group of the graph and the stabilisers of two adjacent vertices.

The form of the information given in the list needs no explanation for items (i) to (v), (vii), (x) and (xi). The form in which the distance partitions (item (iv)) are given can be explained as follows. For a vertex u of a graph X, let N_{i}(u) denote the set of vertices which are at distance i from u. Each such set N_{i}(u) is clearly a union of orbits of the stabiliser (Aut X)_{u}, and sometimes just a single orbit. Let {n_{i,1}, n_{i,2}, …, n_{i,t_{i}}} be the set of lengths of the orbits of N_{i}(u), and let k_{i,j} denote the number of these orbits of length n_{i,j}, for 1 ≤ j ≤ t_{i}. The distance partition of the graph X relative to the vertex u is then defined as the sequence

(n_{0,1}^{k_{0,1}}, n_{1,1}^{k_{1,1}} … n_{1,t_{i}}^{k_{1,t_{i}}} , …, n_{d,1}^{k_{d,1}} … n_{d,t_{i}}^{k_{d,t_{i}}}),

where d is the diameter of the graph X.

Clearly, any two vertices in the same orbit of Aut X have identical distance partitions, and since the automorphism group of a semisymmetric graph has two orbits on vertices, two sequences are given for every graph in our list. If there are no vertices at distance d from u (which can occur if the longest geodesics begin and end in the orbit not containing u), then we take the last symbol in the above sequence to be 0. For example, in the case of the graph S112, it can be read from the sequences (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 1^{1}3^{11}, 3^{8}, 1^{1}3^{2}, 1^{1}) and (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 1^{1}3^{11}, 1^{1}3^{8}, 1^{1}3^{2}, 0) that the number of vertices at distance 6 from a given vertex u is either 8 · 3 = 24 or 8 · 3 + 1 · 1 = 25. The vertex stabiliser (Aut X)_{u} has 8 orbits of length 3 on N_{6}(u) in the first case, and has 8 orbits of length 3 and one of length 1 in the second case.

Information regarding direct covers and direct quotients (items (viii) and (ix)) for each graph X in our list is given in a table with three sections: a top section, a middle section, and a bottom section, with the middle section containing only the name of the graph X.

The bottom section is divided by vertical lines into several subsections, one for each of the direct quotients of the graph X. (If there are no direct quotients, that is, if X is a basic graph, then the bottom section is omitted, and if there is exactly one direct quotient, there is no division into subsections.) Each subsection is again divided into an upper and lower part. The lower part gives the name of the quotient graph, which can be either a semisymmetric cubic graph (appearing elsewhere in the list), or a symmetric cubic graph (appearing in [7]), or K_{1,3}. In the upper part, three pieces of information are given. First, the symbol “Cov” is used to indicate that the quotient projection is a regular covering projection, and otherwise “Quo” is used to indicate that it is not. The second piece of information refers to the largest possible subgroup of Aut X that projects along the quotient projection; “Aut X” is written if this is the full automorphism group Aut X itself, and otherwise only the index of the minimal edge-transitive group of X in this maximal subgroup is given, and denoted by [ : mET|. The third piece of information is a description of the subgroup with respect to which the quotient projection is defined.

Similarly the top section is divided by vertical lines into several subsections, one for each graph in the list which is a direct cover of X. The upper part of each subsection gives the name of the covering graph, while the lower part gives two pieces of information: first, either “Aut X” if Aut X lifts along the covering projection, or otherwise the index | : mET| of the minimal edge-transitive group in the largest subgroup of Aut X that so lifts, and second, the voltage group (the group of covering transformations). If there are no such covering graphs in our list, then this is indicated by two sets of three dots.

The list

S54 (The Gray graph), families III and VII G-Type: G_{2}^{4} additional relations: xyxȳx̄yx̄ȳ

Diam X = 6, Girth X = 8 |Aut X| = 1296 = 2^{4} · 3^{4} |(Aut X)_{u}| = 48 = 2^{4} · 3

Stab-Part: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 4^{1}12^{1}, 12^{1}, 4^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{1}, 12^{1}, 8^{1})

|mET| = 81, solvable (The four Syl 3-subgroups)

S216  S378  S702b
\begin{matrix}| : mET| = 2 \\ ZZ & 2 2 \end{matrix}  \begin{matrix}| : mET| = 1 \\ ZZ & 7 \end{matrix}  \begin{matrix}| : mET| = 1 \\ ZZ & 13 \end{matrix}

X = S54 Cov | : mET| = 4

ZZ^{3}

F18

S110, family II, basic G-Type: G_{2}^{1} additional relations: cd(x̄ȳ)^{2}xȳ(x̄ȳ)^{2}

Diam X = 7, Girth X = 10 |Aut X| = 1320 = 2^{3} · 3 · 5 · 11, P GL(2, 11) |(Aut X)_{u}| = 2^{3} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{1}24^{1}, 12^{2}, 4^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 24^{1}, 12^{1}24^{1}, 4^{1}8^{1}12^{1}, 4^{1})

|mET| = 660, simple, PSL(2, 11)

\begin{matrix}S330 \\ Aut X \\ ZZ & 3 \\ X = S110 \end{matrix}

S112, family IV G-Type: G_{1} additional relations: xyxȳxy(x̄ȳ)^{2}

Diam X = 8, Girth X = 10 |Aut X| = 168 = 2^{3} · 3 · 7 |(Aut X)_{u}| = 3

Stab-Part: (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 1^{1}3^{11}, 3^{8}, 1^{1}3^{2}, 1^{1}) (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 1^{1}3^{11}, 1^{1}3^{8}, 1^{1}3^{2}, 0)

|mET| = 168, solvable

S336a  S448
\begin{matrix}Aut X \\ ZZ & 3 \end{matrix}  \begin{matrix}Aut X \\ ZZ & 2 2 \end{matrix}

X = S112 Cov Aut X

ZZ3 2

F14

S120, family IIV G-Type: G_{1}^{3} additional relations: (xȳx̄ȳ)^{2} Diam X = 8, Girth X = 8 |Aut X| = 720 = 2^{4} · 3^{2} · 5 |(Aut X)_{u}| = 12 = 2^{2} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 6^{1}12^{1}, 6^{2}12^{1}, 3^{1}12^{2}, 3^{1}6^{1}12^{1}, 2^{1}6^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 6^{1}12^{1}, 6^{2}12^{1}, 2^{1}6^{4}, 3^{1}6^{1}12^{1}, 1^{1}2^{1}6^{1})

|mET| = 180, nonsolvable, ZZ_{3} × A_{5} S240 Aut X

ZZ^{2}

X = S120

Cov ; Aut X ; ZZ_{3}  Quo ; Aut X ; A_{5}

F40  K_{1,3}

S126 (Tutte’s 12-cage), basic G-Type: G_{4}^{1} additional relations: a^{3}b(xy)^{3}(x̄ȳ)^{3}

Diam X = 6, Girth X = 12 |Aut X| = 12096 = 2^{6} · 3^{3} · 7, U_{3}(3)˙2 |(Aut X)_{u}| = 192 = 2^{6} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 24^{1}, 48^{1}, 32^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 24^{1}, 48^{1}, 32^{1})

|mET| = 6048, simple, U_{3}(3)

⋯; ⋯; X = S126

S144, family V G-Type: G_{1}^{1} additional relations: (x̄ȳ)^{4}, xyx̄yxyx̄ȳxȳx̄ȳ

Diam X = 8, Girth X = 8 |Aut X| = 432 = 2^{4} · 3^{3} |(Aut X)_{u}| = 6 = 2 · 3

Stab-Part: (1^{1}, 3^{1}, 6^{1}, 6^{2}, 3^{1}6^{3}, 3^{2}6^{5}, 3^{1}6^{6}, 3^{3}6^{2}, 1^{2}3^{1}) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 3^{1}6^{3}, 3^{2}6^{5}, 1^{1}2^{1}3^{3}6^{3}, 3^{3}6^{2}, 2^{1}6^{2})

|mET| = 216, solvable

S432b  S576
\begin{matrix}Aut X \\ ZZ & 3 \end{matrix}  \begin{matrix}Aut X \\ ZZ & 2 2 \end{matrix}

X = S144 Cov Aut X

ZZ2 3

F16

S182, family II, basic G-Type: G_{2}^{1} additional relations: (x̄ȳ)^{6}, cdx̄yxȳx̄ȳx̄y(x̄ȳ)^{2}

Diam X = 8, Girth X = 12 |Aut X| = 2184 = 2^{3} · 3 · 7 · 13, P GL(2, 13) |(Aut X)_{u}| = 24 = 2^{3} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 24^{2}, 12^{2}24^{1}, 4^{1}12^{2}, 12^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 24^{2}, 24^{2}, 8^{1}12^{2}24^{1}, 4^{1}12^{2}, 4^{1})

|mET| = 1092, simple, PSL(2, 13)

S546b ; Aut X ; ^{ZZ^{3}} ; X = S182

S210, basic G-Type: G_{2}^{4} additional relations: cd^{2}ex̄ȳ(x̄yx̄ȳ)^{2}, (x̄ȳ)^{7}

Diam X = 8, Girth X = 10 |Aut X| = 5040 = 2^{4} · 3^{2} · 5 · 7, S_{7} |(Aut X)_{u}| = 48 = 2^{4} · 3

Stab-Part: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{1}24^{1}, 12^{2}24^{1}, 6^{1}24^{2}, 2^{1}24^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 24^{1}, 12^{1}24^{1}, 6^{1}48^{1}, 6^{1}24^{2}, 8^{1}12^{1})

|mET| = 2520, simple, A_{7}

S420  S630
\begin{matrix}Aut X \\ ZZ & 2 \end{matrix}  \begin{matrix}Aut X \\ ZZ & 3 \end{matrix}
X = S210

S216 G-Type: G_{1}^{1} additional relations: (xy)^{3}(x̄ȳ)^{3}, (xȳx̄ȳ)^{3}, x(yx̄)^{4}yxȳx̄ȳ

Diam X = 8, Girth X = 12 |Aut X| = 648 = 2^{3} · 3^{4} |(Aut X)_{u}| = 6 = 2 · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 2^{1}3^{2}6^{10}, 3^{5}6^{5}, 1^{2}2^{2}3^{1}) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 2^{1}3^{2}6^{10}, 3^{5}6^{5}, 3^{3})

|mET| = 324, solvable S432c Aut X

ZZ^{2}

X = S216

Cov ; Aut X ; ZZ_{3}  Cov ; Aut X ; ZZ_{2}^{2}

F72  S54

S220 G-Type: G_{1}^{3} additional relations: cx̄ȳ(xȳx̄ȳ)^{2}, (x̄ȳ)^{6}

Diam X = 10, Girth X = 10 |Aut X| = 1320 = 2^{3} · 3 · 5 · 11 |(Aut X)_{u}| = 12 = 2^{2} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 6^{1}12^{3}, 6^{3}12^{3}, 2^{1}6^{4}12^{2}, 6^{2}12^{1}, 3^{1}, 1^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 6^{1}12^{3}, 6^{5}12^{2}, 2^{1}6^{4}12^{2}, 6^{4}, 3^{1}, 1^{1})

|mET| = 660, simple, PSL(2, 11)

S660 Aut X

ZZ^{3}

X = S220 Cov Aut X

ZZ^{2}

F110

S240 G-Type: G_{1}^{3} additional relations: xȳ(xy)^{2}x̄y(x̄ȳ)^{2}, xyx̄ȳxȳx̄yxȳx̄ȳ

Diam X = 10, Girth X = 12 |Aut X| = 1440 = 2^{5} · 3^{2} · 5 |(Aut X)_{u}| = 12 = 2^{2} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 6^{2}12^{4}, 3^{1}6^{2}12^{3}, 1^{1}2^{1}12^{2}, 6^{1}, 2^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 4^{1}6^{2}12^{4}, 3^{1}6^{2}12^{3}, 1^{1}2^{2}6^{3}, 6^{1}, 2^{1})

|mET| = 360, nonsolvable

⋯

⋯

X = S240

Cov ; Aut X ; ZZ_{2}  Cov ; Aut X ; ZZ_{3}

S120  F80

S294, family III G-Type: G_{1}^{2} additional relations: (xȳx̄ȳ)^{3}, xy(x̄yxȳ)^{2}x̄ȳ, (x̄yx̄ȳ)^{3}

Diam X = 9, Girth X = 12 |Aut X| = 882 = 2 · 3^{2} · 7^{2} |(Aut X)_{u}| = 6 = 2 · 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 6^{2}, 6^{4}, 6^{8}, 3^{4}6^{9}, 3^{4}6^{10}, 1^{2}3^{12}6^{2}, 3^{2}6^{1}) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 2^{1}6^{12}, 3^{4}6^{10}, 3^{2}6^{6}, 3^{2}6^{1})

|mET| = 441, solvable

⋯

⋯

X = S294 Cov mET

ZZ^{7}

F42 S330, family VII G-Type: G_{2}^{1} additional relations: d^{2}x̄yxyx̄y(x̄ȳ)^{3} Diam X = 10, Girth X = 12 |Aut X| = 3960 = 2^{3} · 3^{2} · 5 · 11 |(Aut X)_{u}| = 24 = 2^{3} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 24^{2}, 12^{1}24^{2}, 12^{2}24^{2}, 6^{1}12^{4}, 6^{1}12^{2}, 2^{1}6^{1}12^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 24^{1}, 24^{2}, 8^{1}12^{1}24^{2}, 12^{2}24^{2}, 12^{1}24^{2}, 6^{1}12^{2}, 2^{1}4^{1})

|mET| = 1980, nonsolvable, ZZ_{3} × PSL(2, 11)

⋯

⋯

X = S330

Cov ; Aut X ; ZZ_{3}

Quo Aut X PSL(2, 11)

S110  K_{1,3}

S336a G-Type: G_{1} additional relations: (x̄ȳ)^{6}, (xȳx̄ȳ)^{3}, xy(x̄yxȳ)^{2}x̄ȳ Diam X = 10, Girth X = 12 |Aut X| = 504 = 2^{3} · 3^{2} · 7 |(Aut X)_{u}| = 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{23}, 3^{26}, 1^{2}3^{21}, 3^{9}, 1^{3}) (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 1^{2}3^{25}, 3^{26}, 3^{19}, 3^{9}, 1^{3})

|mET| = Aut X, solvable

⋯

⋯

X = S336a

Cov ; Aut X ; ZZ_{3}  Cov ; Aut X ; ZZ_{2}^{3}

S112  F42

S336b, family VII G-Type: G_{1}^{1} additional relations: xȳ(x̄ȳ)^{2}xȳ(x̄ȳ)^{2}, x̄yxȳxyx̄ȳx̄yx̄ȳ Diam X = 10, Girth X = 12 |Aut X| = 1008 = 2^{4} · 3^{2} · 7 |(Aut X)_{u}| = 6 = 2 · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 2^{1}3^{1}6^{11}, 3^{4}6^{12}, 2^{1}3^{3}6^{9}, 3^{1}6^{3}, 1^{1}) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 3^{3}6^{9}, 3^{4}6^{12}, 2^{1}3^{1}6^{11}, 3^{1}6^{3}, 3^{1})

|mET| = 504, nonsolvable, ZZ_{3} × PSL(2, 7)

S672a Aut X

ZZ^{2}

X = S336b

Cov ; Aut X ; ZZ_{3}

Quo Aut X PSL(2, 7)

F112a  K_{1,3}

S336c, family VII G-Type: G_{1}^{3} additional relations: xy(x̄y)^{2}xȳ(x̄ȳ)^{2}, xȳx̄ȳx̄yxȳxy(x̄ȳ)^{2}

Diam X = 10, Girth X = 12 |Aut X| = 2016 = 2^{5} · 3^{2} · 7 |(Aut X)_{u}| = 12 = 2^{2} · 3 Stab-Part: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 6^{1}12^{6}, 6^{3}12^{6}, 2^{1}6^{7}12^{1}, 3^{1}6^{2}, 1^{1}2^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 6^{1}12^{6}, 6^{3}12^{6}, 2^{1}6^{3}12^{3}, 3^{1}6^{2}, 3^{1})

|mET| = 504, nonsolvable, ZZ_{3} × PSL(2, 7)

S672b Aut X

ZZ^{2}

X = S336c

Cov ; Aut X ; ZZ_{3}  Quo ; Aut X ; P SL(2, 7)

F112b  K_{1,3}

S364 G-Type: G_{1}^{3} additional relations: c(x̄ȳ)^{2}(xȳ)^{2}(x̄ȳ)^{2}, (xyxȳx̄ȳ)^{2} Diam X = 12, Girth X = 12 |Aut X| = 2184 = 2^{3} · 3 · 7 · 13, ZZ_{2} × PSL(2, 13) |(Aut X)_{u}| = 12 = 2^{2} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 6^{1}12^{5}, 6^{4}12^{4}, 6^{3}12^{4}, 2^{1}6^{1}12^{3}, 6^{1}12^{1}, 3^{1}, 1^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 6^{3}12^{4}, 6^{4}12^{4}, 6^{5}12^{3}, 2^{1}6^{1}12^{3}, 6^{1}12^{1}, 3^{1}, 1^{1})

|mET| = 1092, simple, PSL(2, 13)

⋯

⋯

X = S364 Cov Aut X ZZ_{2} = Z(Aut X) F182d

S378 G-Type: G_{1} additional relations: (xy)^{3}(x̄ȳ)^{3}, (xȳx̄ȳ)^{3}, x(yx̄)^{2}(ȳx)^{2}(yx̄)^{4}ȳ Diam X = 10, Girth X = 12 |Aut X| = 567 = 3^{4} · 7 |(Aut X)_{u}| = 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 1^{2}3^{22}, 3^{23}, 3^{24}, 3^{19}, 3^{6}) (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 1^{2}3^{22}, 3^{23}, 3^{24}, 3^{19}, 1^{6}3^{4})

|mET| = Aut X, solvable

⋯

⋯

X = S378

Cov ; Aut X ; ZZ_{3}  Cov ; Aut X ; ZZ_{7}

F126  S54

S384 G-Type: G_{1}^{3} additional relations: (x̄ȳ)^{6}, xyx̄yxyx̄ȳxȳx̄ȳ

Diam X = 10, Girth X = 12 |Aut X| = 2304 = 2^{8} · 3^{2} |(Aut X)_{u}| = 12 = 2^{2} · 3

Stab-Part: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 6^{3}12^{4}, 6^{6}12^{4}, 3^{1}6^{8}12^{3}, 3^{1}6^{1}12^{3}, 2^{1}6^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 4^{1}6^{3}12^{4}, 6^{6}12^{4}, 2^{1}6^{4}12^{4}, 3^{1}6^{1}12^{3}, 1^{1}4^{1}12^{1})

|mET| = 576, solvable

S768a  S768b
\begin{matrix}Aut X \\ ZZ & 2 \end{matrix}  \begin{matrix}Aut X \\ ZZ & 2 \end{matrix}

X = S384 Cov Aut X

ZZ2 2

F96b

S400, family V G-Type: G_{1} additional relations: (x̄ȳ)^{4}, (xȳ)^{6}, xyxȳx̄yx(yx̄)^{2}ȳxȳx̄ȳ Diam X = 10, Girth X = 8 |Aut X| = 600 = 2^{3} · 3 · 5^{2} |(Aut X)_{u}| = 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{7}, 3^{12}, 3^{20}, 3^{32}, 1^{1}3^{36}, 1^{2}3^{17}, 3^{1}) (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{7}, 3^{12}, 3^{20}, 3^{32}, 3^{36}, 1^{2}3^{17}, 1^{1}3^{1})

|mET| = Aut X, solvable

⋯

⋯

X = S400 Cov Aut X

ZZ2 5

F16 S420 G-Type: G_{2}^{4} additional relations: cdx̄yx̄ȳxyxȳx̄yx̄ȳ, (x̄ȳ)^{7} Diam X = 10, Girth X = 12 |Aut X| = 10080 = 2^{5} · 3^{2} · 5 · 7, ZZ_{2} × (mET ⋊ ZZ_{2}) |(Aut X)_{u}| = 48 = 2^{4} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 24^{2}, 12^{1}24^{3}, 12^{2}24^{2}48^{1}, 4^{1}6^{1}12^{1}24^{3}, 3^{1}24^{1}, 1^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 24^{1}, 24^{2}, 12^{1}24^{1}48^{1}, 12^{2}24^{2}48^{1}, 6^{1}8^{1}24^{1}48^{1}, 3^{1}24^{1}, 1^{1}8^{1})

|mET| = 2520, simple, A_{7}

⋯

⋯

X = S420 Cov Aut X ZZ_{2} = Z(Aut X) S210

S432a G-Type: G_{1} additional relations: (xȳx̄y)^{2}(x̄ȳ)^{3}, (xy)^{2}x̄y(xȳ)^{2}(x̄ȳ)^{2} Diam X = 10, Girth X = 14 |Aut X| = 648 = 2^{3} · 3^{4} |(Aut X)_{u}| = 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{32}, 1^{2}3^{39}, 1^{2}3^{26}, 1^{1}3^{11}, 3^{3}) (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{32}, 1^{2}3^{39}, 1^{2}3^{26}, 1^{1}3^{11}, 3^{3})

|mET| = Aut X, solvable

⋯

⋯

X = S432a Cov Aut X

ZZ^{3}

F144a

S432b G-Type: G_{1}^{1} additional relations: (yx)^{6}, xyx̄yxyx̄ȳxȳx̄ȳ, (x̄y)^{2}x̄ȳxyx̄ȳx̄y(x̄ȳ)^{2} Diam X = 10, Girth X = 12 |Aut X| = 1296 = 2^{4} · 3^{4} |(Aut X)_{u}| = 6 = 2 · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 3^{1}6^{12}, 3^{2}6^{19}, 2^{3}3^{1}6^{15}, 3^{3}6^{4}, 1^{2}3^{1}6^{1}) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 2^{2}3^{1}6^{12}, 3^{2}6^{19}, 2^{4}3^{3}6^{14}, 3^{3}6^{4}, 1^{1}2^{2})

|mET| = 648, solvable

⋯

⋯

X = S432b

Cov ; Aut X ; ZZ_{3}  Cov ; Aut X ; ZZ_{3}^{2}

S144  F48

S432c G-Type: G_{1}^{1} additional relations: (xy)^{3}(x̄ȳ)^{3}, x(yx̄)^{4}yxȳx̄ȳ Diam X = 12, Girth X = 12 |Aut X| = 1296 = 2^{4} · 3^{4} |(Aut X)_{u}| = 6 = 2 · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 2^{1}6^{13}, 3^{2}6^{17}, 1^{2}2^{4}6^{14}, 3^{2}6^{6}, 1^{2}2^{1}6^{1}, 3^{1}, 1^{1}) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 2^{1}6^{13}, 3^{2}6^{17}, 3^{4}6^{14}, 3^{2}6^{6}, 2^{1}6^{1}, 3^{1}, 1^{1})

|mET| = 648, solvable

⋯

⋯

X = S432c

Cov ; Aut X ; ZZ_{2}  Cov ; Aut X ; ZZ_{3}

S216  F144b

S448, family IV G-Type: G_{1} additional relations: (x̄ȳ)^{6}, (xȳx̄ȳ)^{3}, (x(yx̄)^{2}ȳ)^{2} Diam X = 10, Girth X = 12 |Aut X| = 672 = 2^{5} · 3 · 7 |(Aut X)_{u}| = 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{26}, 1^{1}3^{36}, 3^{37}, 1^{1}3^{17}, 1^{1}3^{1}) (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{26}, 1^{1}3^{36}, 3^{35}, 1^{1}3^{17}, 1^{1}3^{3})

|mET| = Aut X, solvable

⋯

⋯

X = S448

Cov ; Aut X ; ZZ_{2}^{2}  Cov ; Aut X ; ZZ_{2}^{3}

S112  F56a

S486 G-Type: G_{1}^{1} additional relations: (xy)^{3}(x̄ȳ)^{3}, (xȳx̄ȳ)^{3}, x(yx̄)^{7}yxȳx̄ȳ Diam X = 12, Girth X = 12 |Aut X| = 1458 = 2 · 3^{6} |(Aut X)_{u}| = 6 = 2 · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 2^{1}3^{2}6^{10}, 3^{3}6^{10}, 3^{2}6^{11}, 3^{1}6^{13}, 3^{2}6^{10}, 3^{4}6^{3}, 3^{2}) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 2^{1}3^{2}6^{10}, 3^{3}6^{10}, 3^{2}6^{11}, 3^{1}6^{13}, 3^{2}6^{10}, 3^{4}6^{3}, 3^{2})

|mET| = 729, solvable

⋯

⋯

X = S486 Cov Aut X

ZZ^{3}

F162a

S504, family VII, basic G-Type: G_{1}^{2} additional relations: (x̄ȳ)^{6}, cx̄yxȳxy(xȳ)^{2}(x̄ȳ)^{2} Diam X = 10, Girth X = 12 |Aut X| = 1512 = 2^{3} · 3^{3} · 7, PSL(2, 8) ⋊ ZZ_{3} |(Aut X)_{u}| = 6 = 2 · 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 6^{2}, 6^{4}, 6^{8}, 6^{15}, 6^{22}, 2^{1}3^{6}6^{17}, 3^{3}6^{8}, 1^{2}2^{2}3) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 6^{15}, 6^{22}, 6^{19}, 3^{3}6^{8}, 2^{1}3^{1}6^{2})

|mET| = Aut X, nonsolvable

⋯

⋯

X = S504 Quo Aut X PSL(2, 8) K_{1,3}

S506, family II, basic G-Type: G_{2}^{1} additional relations: cd^{2}(x̄ȳ)^{2}(xy)^{2}(x̄ȳ)^{2} Diam X = 11, Girth X = 12 |Aut X| = 6072 = 2^{3} · 3 · 11 · 23, PSL(2, 23) |(Aut X)_{u}| = 24 = 2^{4} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 24^{2}, 12^{2}24^{2}, 12^{2}24^{3}, 6^{1}12^{3}24^{3}, 4^{1}6^{1}12^{2}24^{2}, 12^{3}, 12^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 24^{1}, 24^{2}, 24^{3}, 12^{2}24^{3}, 8^{1}12^{3}24^{3}, 4^{1}6^{1}12^{2}24^{2}, 4^{1}6^{1}24^{1}, 12^{1})

|mET| = Aut X, simple

⋯; ⋯; X = S506

S546a, family III G-Type: G_{1} additional relations: (xȳx̄ȳ)^{3}, (x̄yx̄ȳ)^{3}, xȳ(xy)^{2}(xȳ)^{2}(x̄ȳ)^{2}, xyxȳx̄yxyx̄ȳxy(x̄ȳ)^{2} Diam X = 10, Girth X = 12 |Aut X| = 819 = 3^{2} · 7 · 13 |(Aut X)_{u}| = 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{28}, 3^{40}, 3^{44}, 3^{30}, 1^{2}3^{8}) (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{28}, 3^{40}, 1^{2}3^{46}, 3^{30}, 3^{6})

|mET| = Aut X, solvable

⋯

⋯

X = S546a

Cov ; Aut X ; ZZ_{7}  Cov ; Aut X ; ZZ_{13}

F78  F42

S546b, family VII G-Type: G_{2}^{1} additional relations: (x̄ȳ)^{6}, cdx(yx̄)^{2}ȳx̄yxȳx̄y(x̄ȳ)^{2} Diam X = 12, Girth X = 12 |Aut X| = 6552 = 2^{3} · 3^{2} · 7 · 13 |(Aut X)_{u}| = 24 = 2^{3} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 24^{2}, 12^{1}24^{3}, 12^{2}24^{5}, 12^{5}24^{3}, 12^{3}24^{1}, 6^{2}12^{1}, 6^{1}, 2^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 24^{1}, 24^{2}, 12^{1}24^{3}, 12^{2}24^{5}, 8^{1}12^{1}24^{5}, 12^{3}24^{1}, 4^{1}12^{1}, 6^{1}, 2^{1})

|mET| = 3276, nonsolvable, ZZ_{3} × PSL(2, 13)

⋯

⋯

X = S546b

Cov ; Aut X ; ZZ_{3}

Quo Aut X PSL(2, 13)

S182  K_{1,3}

S576 G-Type: G_{1}^{1} additional relations: (x̄ȳ)^{4}, (xȳ)^{6}, (xyx̄ȳ)^{4}, xȳ(x̄y)^{2}xȳx(yx̄)^{2}ȳxȳx̄ȳ Diam X = 12, Girth X = 8 |Aut X| = 1728 = 2^{6} · 3^{3} |(Aut X)_{u}| = 6 = 2 · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 6^{2}, 3^{1}6^{3}, 3^{2}6^{5}, 3^{2}6^{9}, 3^{2}6^{15}, 3^{3}6^{22}, 3^{6}6^{19}, 1^{2}3^{2}6^{8}, 3^{1}6^{1}, 3^{1}) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 3^{1}6^{3}, 3^{2}6^{5}, 3^{2}6^{9}, 3^{2}6^{15}, 3^{3}6^{22}, 3^{6}6^{19}, 1^{1}2^{2}3^{3}6^{7}, 3^{1}6^{1}, 3^{1})

|mET| = 864, solvable

⋯

⋯

X = S576

Cov ; Aut X ; ZZ_{2}^{2}  Cov ; Aut X ; ZZ_{3}^{2}

S144  F64

S630 G-Type: G_{2}^{4} additional relations: cd^{2}ex̄ȳ(x̄yx̄ȳ)^{2} Diam X = 14, Girth X = 10 |Aut X| = 15120 = 2^{4} · 3^{3} · 5 · 7 |(Aut X)_{u}| =

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{1}24^{1}, 12^{2}24^{1}, 6^{1}24^{1}48^{1}, 6^{1}48^{2}, 12^{1}24^{2}48^{1}, 24^{4}, 24^{3}, 12^{1}24^{1}, 6^{1}, 2^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 24^{1}, 12^{1}24^{1}, 6^{1}48^{1}, 6^{1}24^{1}48^{1}, 12^{2}24^{1}48^{1}, 12^{1}24^{2}48^{1}, 12^{2}48^{2}, 24^{3}, 12^{1}, 6^{1}, 2^{1})

|mET| = 7560, nonsolvable, ZZ_{3} ⋊ A_{7}

⋯

⋯

X = S630 Cov Aut X

ZZ^{3}

S210

S650, basic G-Type: G_{2}^{4} additional relations: dx̄ȳ(x̄yx̄ȳ)^{2} Diam X = 13, Girth X = 10 |Aut X| = 15600 = 2^{4} · 3 · 5^{2} · 13, PΣL(2, 25) |(Aut X)_{u}| = 24 = 2^{4} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{1}24^{1}, 12^{2}24^{1}, 6^{1}24^{1}48^{1}, 6^{1}48^{2}, 12^{1}24^{2}48^{1}, 12^{1}24^{2}48^{1}, 12^{1}24^{1}48^{1}, 12^{1}24^{1}, 4^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 24^{1}, 12^{1}24^{1}, 6^{1}48^{1}, 6^{1}24^{1}48^{1}, 12^{2}24^{1}48^{1}, 12^{1}24^{2}48^{1}, 8^{1}24^{3}48^{1}, 12^{1}24^{1}48^{1}, 4^{1}12^{1}, 4^{1})

|mET| = 7800, simple, PSL(2, 25)

⋯; ⋯; X = S650

S660, family VII G-Type: G_{1}^{3} additional relations: (x̄ȳ)^{6}, dxȳx̄ȳxyx̄yxȳx̄ȳ Diam X = 12, Girth X = 12 |Aut X| = 3960 = 2^{3} · 3^{2} · 5 · 11 |(Aut X)_{u}| = 12 = 2^{2} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 6^{3}12^{5}, 6^{4}12^{8}, 6^{5}12^{11}, 6^{4}12^{10}, 2^{1}3^{1}6^{1}12^{4}, 3^{1}, 0) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 6^{1}12^{6}, 6^{4}12^{8}, 6^{5}12^{11}, 6^{4}12^{10}, 2^{2}6^{3}12^{3}, 3^{1}, 1^{1})

|mET| = 1980, nonsolvable, ZZ_{3} × PSL(2, 11)

⋯

⋯

X = S660

Cov ; Aut X ; ZZ_{3}

Quo Aut X PSL(2, 11)

S220  K_{1,3}

S672a G-Type: G_{1}^{1} additional relations: xyx̄y(xȳx̄ȳ)^{2}, xȳ(xy)^{3}x̄y(x̄ȳ)^{3} Diam X = 12, Girth X = 12 |Aut X| = 2016 = 2^{5} · 3^{2} · 7 |(Aut X)_{u}| = 6 = 2 · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 3^{2}6^{11}, 3^{2}6^{19}, 2^{1}6^{26}, 3^{2}6^{22}, 3^{2}6^{11}, 3^{1}6^{2}, 1^{1}2^{1}) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 2^{1}6^{13}, 3^{2}6^{19}, 2^{1}3^{4}6^{25}, 3^{2}6^{22}, 2^{1}6^{9}, 3^{1}6^{2}, 1^{1}2^{2})

|mET| = 1008, nonsolvable ZZ_{2} ext_{cent} (ZZ_{3} × PSL(2, 7)) ≅ ZZ_{6} ext_{cent} PSL(2, 7)

⋯

⋯

X = S672a

Cov ; Aut X ; ZZ_{2}  Cov ; Aut X ; ZZ_{3}

S336b  F224b

S672b G-Type: G_{1}^{3} additional relations: xy(x̄y)^{2}xȳ(x̄ȳ)^{2} Diam X = 14, Girth X = 12 |Aut X| = 4032 = 2^{6} · 3^{2} · 7 |(Aut X)_{u}| = 12 = 2^{2} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 6^{1}12^{6}, 6^{2}12^{9}, 2^{1}6^{3}12^{11}, 6^{2}12^{10}, 2^{1}4^{1}6^{2}12^{4}, 6^{1}12^{1}, 2^{1}6^{1}, 3^{1}, 1^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 6^{1}12^{6}, 6^{2}12^{9}, 2^{1}12^{12}, 6^{2}12^{10}, 6^{2}12^{5}, 6^{1}12^{1}, 2^{1}6^{1}, 3^{1}, 1^{1})

|mET| = 1008, nonsolvable ZZ_{2} ext_{cent} (ZZ_{3} × PSL(2, 7)) ≅ ZZ_{6} ext_{cent} PSL(2, 7)

⋯

⋯

X = S672b

Cov ; Aut X ; ZZ_{2}  Cov ; Aut X ; ZZ_{3}

S336c  F224c

S702a G-Type: G_{1} additional relations: (xȳx̄ȳ)^{3}, xyx̄ȳx̄yxy(x̄ȳ)^{4} Diam X = 10, Girth X = 12 |Aut X| = 1053 = 3^{4} · 13 |(Aut X)_{u}| = 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{30}, 3^{56}, 1^{2}3^{66}, 1^{3}3^{39}, 3^{10}) (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{30}, 3^{56}, 3^{64}, 1^{3}3^{39}, 1^{2}3^{12})

|mET| = Aut X, solvable

⋯

⋯

X = S702a Cov Aut X

ZZ3 3

F26

S702b G-Type: G_{1} additional relations: (xy)^{3}(x̄ȳ)^{3}, (xȳx̄ȳ)^{3}, x(yx̄)^{2}ȳxyx̄ȳx(yx̄)^{6}ȳ Diam X = 14, Girth X = 12 |Aut X| = 1053 = 3^{4} · 13 |(Aut X)_{u}| = 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 1^{2}3^{22}, 3^{23}, 3^{24}, 3^{27}, 3^{30}, 3^{33}, 3^{28}, 3^{13}, 3^{2}) (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 1^{2}3^{22}, 3^{23}, 3^{24}, 3^{27}, 3^{30}, 3^{33}, 3^{28}, 3^{13}, 1^{6})

|mET| = Aut X, solvable

⋯

⋯

X = S702b

Cov ; Aut X ; ZZ_{3}  Cov ; Aut X ; ZZ_{13}

F234a  S54

S702c G-Type: G_{1} additional relations: (xy)^{2}x̄ȳxyx̄y(x̄ȳ)^{2} Diam X = 11, Girth X = 14 |Aut X| = 1053 = 3^{4} · 13 |(Aut X)_{u}| = 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{32}, 3^{57}, 3^{68}, 1^{2}3^{38}, 1^{2}3^{6}, 1^{1}) (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{32}, 3^{57}, 1^{2}3^{66}, 1^{2}3^{38}, 3^{8}, 1^{1})

|mET| = Aut X, solvable

⋯

⋯

X = S702c Cov Aut X

ZZ3 3

F26

S720a G-Type: G_{1} additional relations: xy(x̄y)^{2}xȳ(x̄ȳ)^{3}, xȳx̄ȳ(xy)^{2}x̄ȳx̄y(x̄ȳ)^{2} Diam X = 10, Girth X = 14 |Aut X| = 1080 = 2^{3} · 3^{3} · 5, ZZ_{3} ext_{cent} A_{6} |(Aut X)_{u}| = 3

StabPart: (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{32}, 3^{57}, 1^{4}3^{64}, 3^{42}, 1^{1}3^{12}) (1^{1}, 3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{32}, 3^{57}, 1^{2}3^{66}, 3^{42}, 1^{3}3^{10})

|mET| = Aut X, nonsolvable

⋯

⋯

X = S720a Cov Aut X

ZZ^{3}

F240a

S720b, family VII G-Type: G_{1}^{1} additional relations: xy(x̄y)^{2}xȳ(x̄ȳ)^{3}, xyxȳxyx̄ȳxȳx̄y(x̄ȳ)^{2} Diam X = 12, Girth X = 14 |Aut X| = 2160 = 2^{4} · 3^{3} · 5 |(Aut X)_{u}| = 6 = 2 · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 6^{16}, 3^{1}6^{28}, 2^{2}3^{3}6^{29}, 3^{5}6^{18}, 2^{2}3^{4}6^{5}, 3^{1}, 0) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 6^{16}, 3^{1}6^{28}, 2^{4}3^{1}6^{30}, 3^{5}6^{18}, 2^{4}3^{5}6^{3}, 3^{1}, 1^{1})

|mET| = 1080, nonsolvable, ZZ_{3} × A_{6}

⋯

⋯

X = S720b

Cov ; Aut X ; ZZ_{3}  Quo ; Aut X ; A_{6}

F240a  K_{1,3}

S768a G-Type: G_{1}^{1} additional relations: (x̄ȳ)^{6}, xyx̄yxyx̄ȳxȳx̄ȳ, xȳxy(xȳ)^{2}(x̄y)^{3}x̄ȳ Diam X = 12, Girth X = 12 |Aut X| = 2304 = 2^{8} · 3^{2} |(Aut X)_{u}| = 6 = 2 · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 3^{1}6^{12}, 3^{2}6^{19}, 3^{2}6^{27}, 3^{3}6^{29}, 2^{2}3^{2}6^{16}, 3^{2}6^{2}, 1^{1}3^{1}) (1^{1}, 3^{1}, 6^{1}, 6^{2}, 6^{4}, 6^{8}, 2^{2}3^{1}6^{12}, 3^{2}6^{19}, 2^{1}3^{2}6^{26}, 3^{3}6^{29}, 1^{1}2^{5}3^{1}6^{15}, 3^{2}6^{2}, 1^{2}2^{2})

|mET| = 1152, solvable

⋯

⋯

X = S768a

Cov ; Aut X ; ZZ_{2}  Cov ; Aut X ; ZZ_{2}^{2}

S384  S192c

S768b G-Type: G_{1}^{3} additional relations: xyx̄yxyx̄ȳxȳx̄ȳ, (x̄yx̄ȳ)^{3} Diam X = 14, Girth X = 12 |Aut X| = 4608 = 2^{9} · 3^{2} |(Aut X)_{u}| = 12 = 2^{2} · 3

StabPart: (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 6^{2}12^{5}, 6^{4}12^{7}, 3^{1}6^{9}12^{8}, 3^{1}6^{5}12^{11}, 2^{2}6^{9}12^{4}, 3^{1}12^{3}, 1^{1}6^{1}12^{1}, 3^{1}6^{1}, 3^{1}) (1^{1}, 3^{1}, 6^{1}, 12^{1}, 12^{2}, 12^{4}, 4^{1}6^{2}12^{5}, 6^{4}12^{7}, 2^{1}6^{4}12^{11}, 3^{1}6^{5}12^{11}, 1^{1}4^{3}6^{2}12^{6}, 3^{1}12^{3}, 1^{1}6^{3}, 3^{1}6^{1}, 1^{1}2^{1})

|mET| = 1152, solvable

⋯

⋯

X = S768b

Cov ; Aut X ; ZZ_{2}  Cov ; Aut X ; ZZ_{2}^{2}

S384  F192a

8 Voltage rules generating S54, S112 and S120

In this final section we present five diagrams (see Figures 7,8,9,10,11) describing a voltage rule by which the three semisymmetric graphs S54, S112 and S120 are generated from their respective basic (and symmetric) counterparts: F2, F2, and the Petersen graph F10, via a sequence of direct elementary abelian covers; see also Figures 5, 6a and 6b. In the last case, two different routes may be taken, one leading through the dodecahedron F20a and the other through the Desarguesian graph F20b. Furthermore, a voltage rule is also described that gives the graph S120 as a regular (but indirect) D_{3}-cover of F20b.

Figure 7.

Figure 8. Figure 9.

Figure 10. Figure 11.

References

[1] W. Bosma, C. Cannon, and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput. 24 (1997), 235–265.

[2] I.Z. Bouwer, An edge but not vertex transitive cubic graph, Bull. Can. Math. Soc. 11 (1968), 533–535.

[3] I.Z. Bouwer, On edge but not vertex transitive regular graphs, J. Combin. Theory, B 12 (1972), 32–40.

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

[5] M.D.E. Conder and P. Lorimer, Automorphism Groups of Symmetric Graphs of Valency 3, J. Combin. Theory, Series B 47 (1989), 60–72.

[6] M.D.E. Conder, P. Dobcsányi, B. Mc Kay and G. Royle, The Extended Foster Census,

http://www.cs.uwa.edu.au/~gordon/remote/foster/.

[7] M.D.E. Conder and P. Dobcsányi, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput. 40 (2002), 41–63.

[8] M.D.E. Conder, A. Malnič, D. Marušič, T. Pisanski and P. Potočnik, The Ljubljana graph, preprint.

[9] J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker, and R.A. Wilson, Atlas of finite groups, Oxford University Press, Eynsham, 1985.

[10] J.D. Dixon and B. Mortimer, Permutation Groups, Springer-Verlag, New York, 1996.

[11] D.Ž. Djoković and G.L. Miller, Regular Groups of Automorphisms of Cubic Graphs,

[12] P. Dobcsányi, Home Page, http://www.scitec.auckland.ac.nz/~peter.

[13] S.F. Du and D. Marušič, Biprimitive graphs of smallest order, J. Algebraic Combin. 9 (1999), 151–156.

[14] S.F. Du and M.Y. Xu, A classification of semisymmetric graphs of order 2pq (I), Comm. Algebra 28 (2000), 2685–2715. J. Combin. Theory, Series B 29 (1980), 195–230.

[15] J. Folkman, Regular line-symmetric graphs, J. Combin. Theory 3 (1967), 215–232.

[16] R. Frucht, A canonical representation of trivalent Hamiltonian graphs, J. Graph Theory 1 (1977), 45–60.

[17] M. Giudici, C.H. Li and C.E. Praeger, Characterising finite locally s–arc transitive graphs with a star normal quotient, preprint.

[18] C. Godsil, On the full automorphism group of Cayley graphs, Combinatorica 1 (1981), 143–156.

[19] C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer-Verlag, New York, 2001.

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

[21] D. Gorenstein, Finite Groups, Harper and Row, New York, 1968.

[22] D. Gorenstein, Finite Simple Groups: An Introduction To Their Classification, Plenum Press, New York, 1982.

[23] J.L. Gross and T.W. Tucker, Topological Graph Theory, Wiley–Interscience, New York, 1987.

[24] M.E. Iofinova and A.A. Ivanov, Biprimitive cubic graphs, Investigations in Algebraic Theory of Combinatorial Objects (Proceedings of the seminar, Institute for System Studies, Moscow, 1985) Kluwer Academic Publishers, London, 1994, pp 459–472.

[25] A.V. Ivanov, On edge but not vertex transitive regular graphs, Ann. Discrete Math. 34 (1987), 273–286.

[26] M.H. Klin, On edge but not vertex transitive graphs, Coll. Math. Soc. J. Bolyai, (25. Algebraic Methods in Graph Theory, Szeged, 1978), Budapest, 1981, 399–403.

[27] F. Lazebnik and R. Viglione, An infinite series of regular edge- but not vertex-transitive graphs, J. Graph Theory 41 (2002), 249–258.

[28] S. Lipschutz and M.Y. Xu, Note on infinite families of trivalent semisymmetric graphs, European J. Combin. 23 (2002), 707–711.

[29] A. Malnič, D. Marušič, and P. Potočnik, On cubic graphs admitting an edge-transitive solvable group, J. Algebraic Combin., to appear.

[30] A. Malnič, D. Marušič, P. Potočnik, and C.Q. Wang, An infinite family of cubic edge-transitive graphs, Discrete Math., to appear.

[31] A. Malnič, D. Marušič, and P. Potočnik, Elementary abelian covers of graphs, J. Algebraic Combin., to appear.

[32] A. Malnič, R. Nedela, and M. Škoviera, Lifting graph automorphisms by voltage assignments, European J. Combin. 21 (2000), 927–947.

[33] D. Marušič, Constructing cubic edge- but not vertex-transitive graphs, J. Graph Theory 35 (2000), 152–160.

[34] D. Marušič and T. Pisanski, The Gray graph revisited, J. Graph Theory 35 (2000), 1–7.

[35] D. Marušič and P. Potočnik, Semisymmetry of generalized Folkman graphs, European J. Combin. 22 (2001), 333–349.

[36] M. Škoviera, A contribution to the theory of voltage graphs, Discrete Math. 61 (1986), 281–292.

[37] W.T. Tutte, A family of cubical graphs, Proc. Cambridge Phil. Soc. 43(1948), 459–474.

[38] H. Wielandt, Finite Permutation Groups, Academic Press, New York-London, 1964.

[39] S.E. Wilson, A worthy family of semisymetric graphs, Discrete Math., to appear.