Arc-transitive trivalent Cayley graphs (Q2675092)

A combinatorial graph \(\Gamma\) is symmetric, or arc-transitive if its automorphism group acts transitively on the arcs of \(\Gamma\), and \(s\)-arc-transitive (\(s\)-arc-regular) if its automorphism group acts transitively (regularly) on the set of \(s\)-arcs of \(\Gamma\), which are the walks of length \(s\) in \(\Gamma\) in which any three consecutive vertices are distinct. It was shown by \textit{W. T. Tutte} [Proc. Camb. Philos. Soc. 43, 459--474 (1947; Zbl 0029.42401); Can. J. Math. 11, 621--624 (1959; Zbl 0093.37701)] that every finite symmetric trivalent graph is \(s\)-arc regular for some \(s \leq 5\). \textit{D. Ž. Đoković} and \textit{G. L. Miller} [J. Comb. Theory, Ser. B 29, 195--230 (1980; Zbl 0385.05040)] took this further by showing that there are seven types of arc-transitive group actions on finite trivalent graphs, characterised by the stabilisers of a vertex and an edge. The latter classification was refined by \textit{M. Conder} and \textit{R. Nedela} [J. Algebra 322, No. 3, 722--740 (2009; Zbl 1183.05034)], in terms of what types of the arc-transitive subgroup can occur in the automorphism group of \(\Gamma\). In this paper, the authors address the question of when a finite trivalent Cayley graph is symmetric, by determining when a connected finite symmetric trivalent graph is a Cayley graph. To explain this, we need some notation and definitions, as follows. A graph \(\Gamma\) is vertex-transitive if its automorphism group \(\Aut \Gamma\) is transitive on the vertices of \(\Gamma\), and edge-transitive (resp. arc-transitive, or symmetric) if \(\Aut \Gamma\) is transitive on the edges (resp. arcs) of \(\Gamma\). Every vertex-transitive graph is `regular' in the sense of all vertices have the same valency, and when this valency is 3 the graph is called trivalent, or sometimes cubic. A vertex-transitive graph \(\Gamma\) is called a Cayley graph if \(\Aut \Gamma\) contains a subgroup \(G\) that acts sharply-transitively on the vertex-set \(V (\Gamma)\). In this case, we may choose any vertex \(v\) and then let \(S\) be the set of all \(x \in G \) taking \(v\) to one of its neighbours (so that \(|S|\) is the valency of \(\Gamma\)), and then the graph \(\Gamma\) can be constructed by taking its vertices as the elements of \(G\), and its edges as the pairs of the form \(\{g, sg\}\) where \(g \in G\) and \(s \in S\). This set \(S\) is sometimes called the `connection set', and in the given construction, the group \(G\) acts by right multiplication. Next, an \(s\)-arc in \(\Gamma\) is an ordered \((s + 1)\)-tuple \((v_{0}, v_{1},\dots, v_{s-1}, v_{s})\) of vertices of \(\Gamma\) such that every two consecutive \(v_{i}\) are adjacent and any three consecutive \(v_{i}\) are distinct (or in other words, a walk of length \(s\) that never includes the reverse of an arc just used). The graph \(\Gamma\) is then said to be \(s\)-arc-transitive if \(\Aut \Gamma\) is transitive on the set of all \(s\)-arcs in \(\Gamma\). In particular, \(0\)-arc-transitive means the same thing as vertex-transitive, and \(1\)-arc-transitive is the same as arc- transitive, or symmetric. Similarly, an arc-transitive graph \(\Gamma\) is said to be \(s\)-arc-regular if \(\Aut \Gamma\) acts regularly on the set of all \(s\)-arcs in \(\Gamma\). This means that the action of \(\Aut \Gamma\) is sharply-transitive on the arcs of \(\Aut \Gamma\), so that given any two \(s\)-arcs, there is a unique automorphism of \(\Gamma\) mapping the first to the second. For \(s \geq 1\), an \(s\)-arc-regular graph is a union of (disjoint) isomorphic \(s\)-arc-regular connected graphs and isolated vertices. Hence in what follows, only non-trivial connected graphs are considered. Over 60 years ago, it was proved by Tutte [loc. cit.] that every finite symmetric cubic graph \(\Gamma\) is \(s\)-arc-regular for some \(s \leq 5\), and hence that the order of its automorphism group \(\Aut \Gamma\) is bounded above by \(|V (\Gamma)|.3.24 = 48|V (\Gamma)|\). This was taken further by Djoković and Miller, who showed in the year 1980 [loc. cit.] that there are seven types of arc-transitive group actions on connected finite cubic graphs, characterised by the stabilisers of a vertex and an edge. The stabiliser of a vertex in any group \(G\) acting regularly on the \(s\)-arcs of a connected finite cubic graph \(\Gamma\) is isomorphic to either the cyclic group \(C_{3}\), the symmetric group \(S_{3}\), the direct product \(S_{3} \times C_{2}\) (which is dihedral of order 12), the symmetric group \(S_{4}\) or the direct product \(S_{4} \times C_{2}\), depending on whether \(s = 1, 2, 3, 4 \text{ or } 5\). In the cases \(s=2\) and \(s = 4\), there are two different possibilities for the edge-stabilisers (depending on whether or not there exists an automorphism of order 2 reversing an arc), while for \(s=1, 3 \text{ and } 5\) there are just one each. Taking into account the isomorphism type of the pair consisting of the stabilisers of a vertex \(v\) and incident edge \(e = \{v, w\}\), this gives the seven classes (or `types') of arc-transitive actions of a group on a connected finite cubic graph, often denoted by \(1, 2^{1}, 2^{2}, 3, 4^{1}, 4^{2} \text{ and } 5\) (or sometimes instead by \(1^{/}, 2^{/}, 2^{//}, 3^{/}, 4^{/}, 4^{//} \text{ and } 5^{/})\). Here, the types \(s\) and \(s^{1}\) (for \(s \in \{1, 3, 5\}\) and \(s \in \{2, 4\}\) respectively) indicate that the full automorphism group of the graph acts regularly on the \(s\)-arcs, with some automorphism of order 2 reversing an arc, while for the types \(s^{2}\) (for \(s \in \{2, 4\}\)), there is no arc-reversing automorphism of order 2. These classes also correspond to seven classes of `universal' groups acting arc transitively on the infinite cubic tree with finite vertex-stabiliser. It follows that the automorphism group of any connected finite symmetric cubic graph is a homomorphic image of one of these seven groups, which we called \(G_{1}\), \(G_{2}^{1}\), \(G_{2}^{2}\), \(G_{3}\), \(G_{4}^{1}\), \(G_{4}^{2}\) and \(G_{5}\) and analysed in [\textit{M. Conder} and \textit{P. Lorimer}, J. Comb. Theory, Ser. B 47, No. 1, 60--72 (1989; Zbl 0682.05036)] (who found the first known examples of graphs in the two classes \(2^{2}\) and \(4^{2}\)). This classification was refined by \textit{M. Conder} and \textit{R. Nedela} [J. Algebra 322, No. 3, 722--740 (2009; Zbl 1183.05034)], in terms of what types of arc-transitive subgroups can occur in the automorphism group of \(\Gamma\). For example, if \(\Gamma\) is a 3-arc-regular cubic graph, then \(\Aut \Gamma\) might contain a \(2\)-arc-regular subgroup that acts on \(\Gamma\) with type \(2^{1}\), but no \(2\)-arc-regular subgroup that acts with type \(2^{2}\), and no 1-arc-regular subgroup (acting with type 1), in which case we say the action type of \(\Gamma\) is \((2^{2}, 3)\). It was shown in the year 2009 [Conder and Nedela, loc. cit.] that there are exactly 17 different possible action types, as follows: 1-arc-regular \(\Gamma\) \(\quad \quad\) Action type: (1) 2-arc-regular \(\Gamma\) \(\quad \quad\) Action types: \((1, 2^{1}), (2^{1}) \text{ and } (2^{2})\) 3-arc-regular \(\Gamma\) \(\quad \quad\) Action types: \((1, 2^{1}, 2^{2}, 3), (2^{1}, 2^{2}, 3), (2^{1}, 3), (2^{2}, 3) \text{ and } (3)\) 4-arc-regular \(\Gamma\) \(\quad \quad\) Action types: \((1, 4^{1}), (4^{1}) \text{ and } (4^{2})\) 5-arc-regular \(\Gamma\) \(\quad \quad\) Action types: \((1, 4^{1}, 4^{2}, 5), (4^{1}, 4^{2}, 5), (4^{1}, 5), (4^{2}, 5) \text{ and } (5)\) In this paper, the author investigates conditions under which a symmetric cubic graph with a given action type can be a Cayley graph. It turns out that in five of the 17 cases there is no Cayley graph, while in two others, every example is a Cayley graph, and in eight of the remaining ten cases there are necessary conditions on the order of the graph, while in the remaining two cases (namely those where the action type of \(\Gamma\) is \((1)\) or \((1, 2^{1})\), there is no such condition. The author discusses the main result in a case-by-case analysis in Section 3, after giving some background results in Section 2. This paper contains results that are an amalgamation of concepts of graph theory and algebra. The paper is well written. It contains a wealth of results that will inspire any researcher to write a similar paper.