Open Collections

Symmetric Cubic Graphs as Cayley Graphs

Banff International Research Station for Mathematical Innovation and Discovery

A graph $X$ is {\em symmetric} if its automorphism group acts transitively on the arcs of $X$, and {\em $s$-arc-transitive} if its automorphism group acts transitively on the set of $s$-arcs of $X$. Furthermore, if the latter action is sharply-transitive on $s$-arcs, then $X$ is {\em $s$-arc-regular.} It was shown by Tutte (1947, 1959) that every finite symmetric cubic graph is $s$-arc-regular for some $s\leq 5$. Djokovi\v c and Miller (1980) took this further by showing that there are seven types of arc-transitive group action on finite cubic graphs, characterised by the stabilisers of a vertex and an edge. The latter classification was refined by Conder and Nedela (2009), in terms of what types of arc-transitive subgroup can occur in the automorphism group of $X$. In this talk we consider the question of when a finite symmetric cubic graph can be a Cayley graph. We show that in five of the $17$ Conder-Nedela classes, there is no Cayley graph, while in two others, every graph is a Cayley graph. In eight of the remaining ten classes, we give necessary conditions on the order of the graph for it to be Cayley; there is no such condition in the other two. Also we use covers (and the `Macbeath trick') to show that in each of those last ten classes, there are infinitely many Cayley graphs, and infinitely many non-Cayley graphs. This research grew out of some recent discussions with Klavdija Kutnar and Dragan Maru{\v s}i{\v c}.

Mathematics; Convex and discrete geometry; Group theory and generalizations; Discrete mathematics

video/mp4

Author affiliation: University of Auckland

2018-03-23

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/64888

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/