s-arc-transitive graphs

Alice Devillers, Cai Heng Li and Cheryl Praeger and I submitted a paper last week entitled `An infinite family of biquasiprimitive 2-arc transitive cubic graphs‘. In this post I will outline the program into which the paper fits. Some of this was covered in my 33ACCMCC plenary talk.

A s-arc in a graph is an (s+1)-tuple $(v_0,v_1,\ldots,v_s)$ of vertices such that $v_i$ is adjacent to $v_{i+1}$ but $v_{i+2}\neq v_i$ , that is, it is a path in the graph which cannot immediately go back upon itself. A graph $\Gamma$ is called s-arc-transitive if $\mathrm{Aut}(\Gamma)$ acts transitively on the set of s-arcs in $\Gamma$ . If each vertex has valency at least two then every vertex has an s-arc starting at it and every (s-1)-arc can be extended to an s-arc. Hence if $\Gamma$ is s-arc-transitive then it is also (s-1)-arc-transitive. In particular, $\mathrm{Aut}(\Gamma)$ acts transitively on the set of arcs of $\Gamma$ , that is the set of ordered pairs of adjacent vertices, and on the set of vertices.

The complete graph $K_n$ , for $n\geq 4$ is 2-arc-transitive. However, it is not 3-arc-transitive as it contains two types of 3-arcs: those whose first vertex is equal to its last those and those for which the first vertex is distinct from the last vertex. A cycle is s-arc-transitive for all s.

The study of s-arc-transitive graphs was begun by Tutte [5,6], who showed that for cubic graphs (that is those of valency 3), we have $s\leq 5$ . This bound is met by the Tutte-Coxeter graph which is the point-line incidence graph of the generalised quadrangle $W(3,2)$ . With the aid of the classification of 2-transitive groups and hence using the classification of finite simple groups, Weiss[7] proved that for graphs with valency at least 3, we have $s\leq 7$ . The bound is met by the point-line incidence graphs of the classical generalised hexagons associated with the groups $G_2(q)$ .