The smallest symmetric cubic graphs with given type (Q2216562)

This paper concerns highly symmetric cubic graphs. The basic setup is as follows: we say that a graph is symmetric if its automorphism group acts transitively on pairs consisting of a vertex and an incident edge. This paper is devoted to symmetric finite cubic graphs, for which there exists a good structure theory: given such a graph, its automorphism group is known to act regularly on \(k\)-arcs for some \(1\leqslant k\leqslant5\). This naturally divides the set of symmetric cubic graphs into five types. The types for \(k=2,4\) are further subdivided according to the action of an edge-stabiliser. So there are seven classes, labelled \(1\), \(2^1\), \(2^2\), \(3\), \(4^1\), \(4^2\), \(5\). In [\textit{M. Conder} and \textit{R. Nedela}, J. Algebra 322, No. 3, 722--740 (2009; Zbl 1183.05034)], the classes are further subdivided according to the existence of subgroups of the automorphism group which act in each of these seven ways. They showed that there are seventeen possible action types (each of which corresponds to a non-empty subset of \(\{1, 2^1, 2^2, 3, 4^1, 4^2, 5\}\)). They found an example of a graph with each action type, and in fourteen of the cases showed that their example is the smallest. The object of the paper under review is to find the smallest example for each of the other three action types. The method is via computational group theory: it is known that for each of the seven basic types there is a finitely-presented group which is universal in the sense that the automorphism group of any finite cubic graph of that type is a quotient. So the object is to find suitable quotients of these groups. This is done efficiently using MAGMA. The paper is well written, but should not be used as an introduction to the subject; it should be read as a sequel to [loc. cit.].