A refined classification of symmetric cubic graphs

A graph Gamma is symmetric if its automorphism group acts transitively oil the arcs of Gamma, and s-regular if its automorphism group acts regularly on the set of s-arcs of Gamma. Tutte (1947, 1959) showed that every finite symmetric cubic graph is s-regular for some s <= 5. Djokovit and Miller (1980) proved that there are seven types of arc-transitive group action on finite cubic graphs, characterised by the stabilisers of a vertex and an edge. A given finite symmetric cubic graph, however, may admit more than one type of arctransitive group action. In this paper we determine exactly which combinations of types are possible. Some combinations are easily eliminated by existing theory, and others can be eliminated by elementary extensions of that theory. The remaining combinations give 17 classes of finite symmetric cubic graph, and for each of these, we prove the class is infinite, and determine at least one representative. For at least 14 of these 17 classes the representative we give has the minimum possible number of vertices (and we show that in two of these 14 cases every graph in the class is a cover of the smallest representative), while for the other three classes, we give the smallest examples known to us. In an appendix, we give a table showing the class of every symmetric cubic graph on up to 768 vertices. (C) 2009 Elsevier Inc. All rights reserved.