Cubic Vertex-Transitive Graphs Admitting Automorphisms of Large Order

Abstract

A connected graph of order n admitting a semiregular automorphism of order n/k is called a k-multicirculant. Highly symmetric multicirculants of small valency have been extensively studied, and several classification results exist for cubic vertex- and arc-transitive multicirculants. In this paper, we study the broader class of cubic vertex-transitive graphs of order n admitting an automorphism of order n/3 or larger that may not be semiregular. In particular, we show that any such graph is either a k-multicirculant for some $k \le 3$, or it belongs to an infinite family of graphs of girth 6.

1 Introduction

Studying the structure of the automorphism groups of highly symmetrical graphs is one of the classical topics in the area of algebraic graph theory and a very important part of it aims at proving upper bounds on the order of the automorphism groups in terms of a conveniently tame function of the order of the graph (see, for example, the classical work of Tutte [32] on cubic symmetric graphs). Existence of such bounds often allows strong group theoretical tools to be applied.

In some applications (such as a construction of a complete list of all graphs of fixed valence, bounded order and given symmetry type; see for example [7, 23]), a bound on the order of the automorphism group can be substituted with a weaker result where the order of individual automorphisms is bounded rather than the order of the automorphism group itself. It is well known that the order of the automorphism group of a connected vertex-transitive graph of valence 3 (cubic vertex-transitive graph, for short) cannot be bounded by any subexponential function of the order (see, for example, [23]). However, a recent result [27, Theorem 1.6] shows that the order o(g) of an individual automorphism g of a cubic vertex-transitive graph other than $K_{3,3}$ equals the length $\ell (g)$ of the longest orbit of the cyclic group $\langle g \rangle$, implying that o(g) cannot exceed the order of the graph. In other words, if we define

$$\begin{aligned} {\eta }({\Gamma }):= \frac{ |\textrm{V}(\Gamma )|}{\max \{ o(g): g \in \textrm{Aut}(\Gamma )\} }, \end{aligned}$$

then $\eta \mathrm (\Gamma ) \ge 1$ holds for every cubic vertex-transitive graph. The aim of this paper is to investigate how sharp this bound is and under what additional assumptions it can be improved. More precisely, we obtain a complete classification of cubic vertex-transitive graphs $\Gamma$ for which $1 \le \eta \mathrm (\Gamma )\le 3$ holds and thus show that $\eta \mathrm (\Gamma ) > 3$ for every cubic vertex-transitive graph not belonging to a known list of exceptional families (see Theorem 1.1).

Before stating Theorem 1.1, let us first introduce a few notions appearing in its statement. A non-trivial automorphism g of a graph is called semiregular provided that the length of every vertex-orbit of $\langle g \rangle$ equals o(g), or equivalently, when all the orbits of $\langle g \rangle$ have equal size. A graph admitting a semiregular automorphism with k vertex orbits is called a k-multicirculant; in addition, every graph on n vertices is an n-multicirculant. Let

$$\begin{aligned} \kappa (\Gamma ):= \min \{ k\,:\, \Gamma \hbox { is a } k\hbox {-multicirciulant} \} \end{aligned}$$

and observe that $\eta \mathrm (\Gamma )\le \kappa (\Gamma ) \le |\textrm{V}(\Gamma )|$ holds for every graph $\Gamma$. What is more, the well-known polycirculant conjecture [16] (which is known to be true for graphs of valence 3 [17], as well as many other classes of graphs; see [1]) states that $\kappa (\Gamma ) < |\textrm{V}(\Gamma )|$ for every vertex-transitive graph $\Gamma$. There are numerous classification results proved about cubic vertex-transitive k-multicirculants of different symmetry types (see for example [6, 9, 10, 12,13,14,15]) and in particular, all cubic vertex-transitive 1-multicirculants (also called circulants), 2-multicirculant (also called bicirculants) and 3-multicirculants (also called tricirculants) are known [22, 24].

An interesting interplay between the parameters $\eta (\Gamma )$ and $\kappa (\Gamma )$ is considered in Sect. 8. In particular, the question whether the parameter $\kappa (\Gamma )$ can be bounded above in terms of $\eta (\Gamma )$ is discusses there.

Let us now introduce some families of graphs appearing in Theorem 1.1. For a positive integer $n\ge 3$, let $\textrm{Prism}(n)$ denote the prism on 2n vertices, which can also be viewed as the generalised Petersen graph $\textrm{GP}(n,1)$, and let $\textrm{Moeb}(n)$, $n\ge 4$ even, be the Möbius ladder with vertex-set $\mathbb {Z}_n$ and edges of the form $\{x,x+s\}$ for $x\in \mathbb {Z}_n$, $s\in \{\pm 1, n/2\}$. Note that $\kappa (\textrm{Moeb}(n)) = 1$ for every n, while $\kappa (\textrm{Prism}(n))$ is 1 or 2, depending on whether n is odd or even, respectively.

Further, for a positive integer n and distinct elements $i,j \in \mathbb {Z}_n{\setminus } \{0\}$, let $\textrm{H}(n,i,j)$ be the graph with vertex-set $\mathbb {Z}_n\times \mathbb {Z}_2$ and edges of the form $\{ (x,0), (x+s,1)\}$ for $x\in \mathbb {Z}_n$ and $s\in \{0,i,j\}$. Note that the graphs $\textrm{H}(n,i,j)$ are bipartite bicirculants and are also known as cyclic Haar graphs [22]. Clearly, $\kappa (\textrm{H}(n,i,j)) \le 2$ and the values of n, i, j for which $\kappa (\textrm{H}(n,i,j)) = 1$ are characterised in Lemma 7.1.

Let us now define two families of tricirculants, first introduced in [24, Definitions 4.1 and 5.1]. For an odd integer k, $k > 1$, let $\textrm{X}(k)$ be the graph with 6k vertices, labelled $u_i$, $v_i$ and $w_i$ for $i\in \mathbb {Z}_{2k}$, and the edge-set being the union $E_1\cup E_2 \cup E_3 \cup E_4 \cup E_5$ where: $E_1 = \{ \{u_i, u_{i+k}\}: i \in \mathbb {Z}_{2k}\}$, $E_2 = \{ \{u_i,v_i\}: i \in \mathbb {Z}_{2k}\}$, $E_3 = \{ \{u_i,w_i\}: i \in \mathbb {Z}_{2k}\}$, $E_4 = \{ \{v_i,w_{i+1}\}: i \in \mathbb {Z}_{2k}\}$, and $E_5 = \{ \{v_i,w_{i+r}\}: i \in \mathbb {Z}_{2k}\}$, where $r=(k+3)/2$ if $k\equiv 1\> (\hbox {mod}\, 4)$ and $r=(k+3)/2 + k$ if $k\equiv 3\> (\hbox {mod}\, 4)$.

Further, for an odd integer k, $k > 1$, let $\textrm{Y}(k)$ be the graph with 6k vertices, labelled $u_i$, $v_i$ and $w_i$ for $i\in \mathbb {Z}_{2k}$, and the edge-set being the union $E_1\cup E_2 \cup E_3 \cup E_4 \cup E_5$ where: $E_1 = \{ \{u_i, u_{i+1}\}: i \in \mathbb {Z}_{2k}\}$, $E_2 = \{ \{u_i,v_i\}: i \in \mathbb {Z}_{2k}\}$, $E_3 = \{ \{v_i,w_i\}: i \in \mathbb {Z}_{2k}\}$, $E_4 = \{ \{v_i,w_{i+2}\}: i \in \mathbb {Z}_{2k}\}$, and $E_5 = \{ \{w_i,w_{i+k}\}: i \in \mathbb {Z}_{2k}\}$.

By [24, Theorem 4.3 and Theorem 5.3], $\kappa (\textrm{X}(k))=\kappa (\textrm{Y}(k)) =3$ for $k \equiv 3 \> (\hbox {mod}\, 6)$ while $\kappa (\textrm{X}(k))=\kappa (\textrm{Y}(k)) =2$ for $k \equiv 0 \> (\hbox {mod}\, 6)$. More facts about graphs $\textrm{X}(k)$ and $\textrm{Y}(k)$ can be found in [24, Sects. 4 and 5].

For positive integers $m, t \ge 3$, let $\textrm{SDW}(m,t)$ be the cubic graph with the vertex-set $\mathbb {Z}_m\times \mathbb {Z}_t \times \mathbb {Z}_2$ and edges of the form $\{(x,i,0),(x,i\pm 1,1)\}$ and $\{(x,i,1),(x+1,i,0)\}$ for all $x\in \mathbb {Z}_m$ and $i\in \mathbb {Z}_t$. (The graphs $\textrm{SDW}(m,t)$ with $t=3$ are also known as split depleted wreath graphs.) Note that a graph $\textrm{SDW}(m,t)$ is a 2t-multicirculant, as witnessed by the semiregular automorphism of order m, mapping a vertex (x, i, j) to the vertex $(x+1,i,j)$ for every x, i, j. It can be easily seen that $\kappa (\textrm{SDW}(m,3)) \le 6$ and that $\eta \mathrm (\text {SDW}(m,3)) \le 3$ unless m is divisible by 6 (in which case $\eta \mathrm (\text {SDW}(m,3)) = 6$); see Lemma 6.13 for more details.

Finally, Tutte’s 8-cage is the unique cubic arc-transitive graph on 30 vertices, appearing under the name CubicVTgraph(30, 8) in [23], while the truncated tetrahedron is the graph on 12 vertices obtained by the geometric truncation of the skeleton of the tetrahedron (it appears under the name CubicVTgraph(12, 2) in [23]).

We can now state the main result of this paper.

Theorem 1.1

Let $\Gamma$ be a finite simple connected vertex-transitive graph of valence 3 and order n. Then, $\Gamma$ admits an automorphism of order at least $\frac{n}{3}$ (or equivalently, ${\eta }(\Gamma ) \le 3$) if and only if one of the following happens:

• (1) $\kappa (\Gamma ) = 1$ and $\Gamma$ is isomorphic to

  • (a) the prism $\textrm{Prism}(m)$ where $n=2m$ with $m\ge 3$, m odd; or

  • (b) the Möbius ladder $\textrm{Moeb}(n)$ with $n\ge 4$;

• (2) $\kappa (\Gamma ) =2$ and $\Gamma$ is isomorphic to

  • (a) the prism $\textrm{Prism}(m)$ where $n=2m$ with $m\ge 4$, m even;

  • (b) a generalised Petersen graph $\textrm{GP}(m,r)$ where $n=2\,m$, $m\ge 5$, $2\le r < m/2$, and

    • $m \ge 3$, $r^2 \equiv \pm 1$ $(\hbox {mod}\, m)$, or

    • $m = 10$ and $r=2$;

  • (c) the cyclic Haar graphs $\textrm{H}(m;r,s)$ where $n=2m$ with $m \ge 3$, $1 \le r, s \le m-1$, $r\not = s$, r divides m, $\gcd (r,s)=1$, such that m is even or m is odd and $\{r,s\}$ is neither $\{1,m-1\}$ nor $\{1,2\}$.

• (3) $\kappa (\Gamma ) = 3$ and $\Gamma$ is isomorphic to one of the following graphs:

  • (a) $\textrm{X}(k)$ with $k\equiv 3\> (\hbox {mod}\, 6)$;

  • (b) $\textrm{Y}(k)$ with $k\equiv 3\> (\hbox {mod}\, 6)$;

  • (c) Tutte’s 8-cage where $n=30$;

  • (d) the truncated tetrahedron where $n=12$.

• (4) $\kappa (\Gamma ) = 6$ and $\Gamma \cong \textrm{SDW}(m,3)$ with $m\equiv 3$ $(\hbox {mod}\, 6)$, $m\ge 9$, $n=6\,m$.

Remark 1.2

If $\Gamma$ is a graph appearing in one of items (1)–(3), then $\kappa (\Gamma ) = {\eta }(\Gamma )$ except when $\Gamma$ is isomorphic to

• the cube graph $\textrm{Q}_3 \cong \textrm{Prism}(4)$ where ${\eta }\mathrm (\Gamma ) = \frac{4}{3}$;

• the Petersen graph $\textrm{GP}(5,2)$ where ${\eta }\mathrm (\Gamma ) = \frac{5}{3}$;

• the Heawood graph $\textrm{H}(7,1,3)$ where ${\eta }\mathrm (\Gamma ) = \frac{7}{4}$;

• the Möebius–Kantor graph $\textrm{GP}(8,3)$ where ${\eta }\mathrm (\Gamma ) = \frac{4}{3}$;

• the Pappus graph $\textrm{Y}(3) \cong \textrm{SDW}(3,3)$ where ${\eta }\mathrm (\Gamma ) = \frac{3}{2}$.

If $\Gamma$ is one of the graphs in item (4), then ${\eta }(\Gamma ) = 3$. The relation between the functions ${\eta }$ and $\kappa$ is further discussed in Sect. 8.

The proof of the above theorem is inevitably rather technical since a certain amount of case-by-case analysis cannot be avoided. However, we have tried to use as many theoretical tools as possible in order to shorten and organise the arguments into self-contained parts.

Our proof relies on two crucial ideas. The first idea is to classify cubic vertex-transitive graphs $\Gamma$ admitting an automorphism g of order at least $|\textrm{V}(\Gamma )|/3$ in terms of the quotient graphs $\Gamma /\langle g \rangle$. For this approach to be practical, we need to store enough information that will allow us to reconstruct the graphs $\Gamma$ from their quotients. Here, a recently developed theory of generalised cyclic covering projections [25], briefly summarised in Sect. 3, provided the needed theoretical background. The second crucial fact making this approach feasible follows from the results of [27], from which one can deduce that a cyclic group of automorphisms of a cubic vertex-transitive graph $\Gamma$ with order at least $\frac{|\textrm{V}(\Gamma )|}{3}$ can have at most 5 orbits on $\textrm{V}(\Gamma )$ (see Lemma 4.1). In particular, there is only a finite number of possible quotients $\Gamma /\langle g \rangle$ with $o(g) \ge \frac{|\textrm{V}(\Gamma )|}{3}$. The rest of the proof is then a careful case-by-case analysis of these possible quotient graphs. The strategy of proving Theorem 1.1 is laid out in more detail in Sect. 2.3.

2 Overview and Basic Definitions

The following paragraphs, in which we give some basic formal definitions and we outline the proof of Theorem 1.1, serve as a more detailed summary of the contents of this paper.

2.1 Graphs

We would first like to stress that all the graphs in this paper are finite. Even though we are primarily interested in simple graphs (that can be defined as a finite set of vertices together with an irreflexive symmetric relation on it), it will be very convenient for us to adopt a more general definition of a graph that has become standard when quotients and covers of graphs are considered (see, for example, [18]).

For us, a graph is an ordered 4-tuple $(V,D; \mathop {\textrm{beg}},\mathop {\textrm{inv}})$ where D and $V \ne \emptyset$ are disjoint finite sets of darts and vertices, respectively, $\mathop {\textrm{beg}}:D \rightarrow V$ is a mapping which assigns to each dart x its initial vertex $\mathop {\textrm{beg}}\,x$, and $\mathop {\textrm{inv}}$ is an involutory permutation of D which interchanges every dart x with its inverse dart, also denoted by $x^{-1}$. The final vertex of a dart x is $\mathop {\textrm{beg}}x^{-1}$ and is denoted $\mathop {\textrm{end}}x$. The neighbourhood of a vertex v is defined as the set of darts that have v for its initial vertex and the valence of v is the cardinality of the neighbourhood. If $\Gamma$ is a graph we write $\textrm{V}(\Gamma )$ and $\textrm{D}(\Gamma )$ to denote the vertex- and dart-set of $\Gamma$, respectively. Furthermore, we may write $\mathop {\textrm{beg}}_{\Gamma }$ and $\mathop {\textrm{inv}}_{\Gamma }$, with a subscript, to indicate the beginning and inverse functions of $\Gamma$, to avoid confusion when more than one graph is involved. We will generally omit the subscript if there is no possibility of ambiguity.

The orbits of $\mathop {\textrm{inv}}$ are called edges. The edge $\{x,x^{-1}\}$ containing a dart x is called a semi-edge if $x^{-1} = x$, a loop if $x^{-1} \ne x$ while $\mathop {\textrm{beg}}\,(x^{-1}) = \mathop {\textrm{beg}}\,x$, and is called a link otherwise. The endvertices of an edge are the initial vertices of the darts contained in the edge. If $\{u,v\}$ is the set of the endvertices of an edge, then we say that u and v are adjacent and write $u \sim v$. Two darts x and y are parallel if $\mathop {\textrm{beg}}x = \mathop {\textrm{beg}}y$ and $\mathop {\textrm{beg}}x^{-1} = \mathop {\textrm{beg}}y^{-1}$. Two edges are parallel if they have the same endvertices. When we present a graph as a drawing, the links are drawn in the usual way as a line between the points representing its endvertices, a loop is drawn as a closed curve at its unique endvertex and a semi-edge is drawn as a segment attached to its unique endvertex.

A graph without loops, semi-edges and pairs of parallel edges is simple. Note that a simple graph is completely determined by its vertex-set and the adjacency relation, and conversely, given a set V and an irreflexive symmetric relation $\sim$ on V, we can define a graph $(V,D; \mathop {\textrm{beg}},\mathop {\textrm{inv}})$ by letting $D:= \{ (u,v) :u,v \in \textrm{V}(\Gamma ), u\sim v\}$, $\mathop {\textrm{beg}}(u,v) = u$ and $\mathop {\textrm{inv}}(u,v) = (v,u)$. A dart in a simple graph is traditionally called an arc, so we will use these two terms interchangeably. In this paper, a cubic graph will always stand for a connected simple graph in which every vertex has valence 3.

Notions such as morphism, isomorphism and automorphism of graphs are obvious generalisations of those defined in the traditional setting and precise definitions can be found in [18, 19]. In particular, an automorphism of a graph $(V,D; \mathop {\textrm{beg}},\mathop {\textrm{inv}})$ is a permutation g of $V\cup D$ preserving each of V and D such that $\mathop {\textrm{inv}}(x^g) = \mathop {\textrm{inv}}(x)^g$ and $\mathop {\textrm{beg}}(x^g) = \mathop {\textrm{beg}}(x)^g$ for every $x\in D$. Note that when the graph is simple, an automorphism is uniquely defined by its adjacency preserving action on the vertex-set. We shall thus often view automorphism of simple graphs in the usual way, that is, as adjacency preserving permutations of the vertex-set.

2.2 Labelled Quotients of Graphs

Let $\Gamma :=(V,D; \mathop {\textrm{beg}},\mathop {\textrm{inv}})$ be a graph admitting a cyclic group of automorphisms $G \le \textrm{Aut}(\Gamma )$. For $v \in V$, let $v^G$ denote the G-orbit of v and let V/G be the set of all G-orbits of vertices of $\Gamma$. Similarly, let $x^G$ be the G-orbit of $x \in D$ and let D/G be the set of all G-orbits on darts. We define the G-quotient of $\Gamma$ as the graph $\Gamma /G=(V/G,D/G,\mathop {\textrm{beg}}',\mathop {\textrm{inv}}')$ where $\mathop {\textrm{beg}}' x^G = (\mathop {\textrm{beg}}x)^G$ and $\mathop {\textrm{inv}}' x^G = (\mathop {\textrm{inv}}x)^G$ for all $x \in \textrm{D}(\Gamma )$.

Let $x \in \textrm{D}(\Gamma )$ be a dart and let $u = \mathop {\textrm{beg}}x$. Then, $x^G$ is a dart of $\Gamma / G$ with initial vertex $u^G$. Let $\lambda _G(x^G)$ denote the number of darts of $\Gamma$ in the orbit $x^G$ that begin at any fixed vertex in $u^G$ (note that this is independent of which vertex of $u^G$ we choose and that $\lambda _G(x^G) = |x^{G_u}|$). Then, $\lambda _G :\textrm{D}(\Gamma /G) \rightarrow \mathbb {N}$ is a well-defined function and the pair $(\Gamma /G, \lambda _G)$ is called a labelled quotient (see Fig. 1).

Fig. 1

The Möbius ladder on 8 vertices (top left) and $K_{3,3}$ (top right) above their labelled quotients by a cyclic group of automorphisms $G = \langle g \rangle$. For the case on the left, g is the automorphism given by the permutation $(u_0u_1u_2u_3)(v_0v_1v_2v_3)$; for the graph on the right g is given by $(u_0u_1)(v_0v_1v_2)$. In the graph on the lower right, the edge joining $u_0^G$ and $v_0^G$ has a label next to each of its endvertices: 3 next to $u_0^G$, and 2 next to $v_0^G$. These are the labels $\lambda _G(x)$ and $\lambda _G(x^{-1})$ where x is the dart pointing from $u_0$ to $v_0$. This indicates that every vertex in the fibre of $u_0^G$ (in the graph above) has 3 neighbours in the fibre of $v_0^G$ while every vertex in the fibre of $v_0^G$ has 2 neighbours in the fibre of $u_0^G$

2.3 Strategy

In what follows, we describe our plan to prove Theorem 1.1. We first consult the census of all cubic vertex-transitive graphs [23] and check that the theorem holds for all the graphs on at most 20 vertices (this can be easily done with a help of computer and a computer algebra system such as Sage [31]).

We may thus concentrate on the class ${{\mathcal {G}}}$ of all cubic vertex-transitive graphs on at least $n > 20$ admitting a cyclic group $G \le \textrm{Aut}(\Gamma )$ of order at least $\frac{n}{3}$. Let ${{\mathcal {Q}}}$ be the set of labelled quotients $(\Gamma /G, \lambda _G)$ where $\Gamma \in {{\mathcal {G}}}$ and $G \le \textrm{Aut}(\Gamma )$ is cyclic of order at least $\frac{|\textrm{V}(\Gamma )|}{3}$ (by [27, Theorem 4.7], the order of G equals the order of the largest G-orbit on vertices).

Observe that if $(\Gamma /G, \lambda _G) \in {{\mathcal {Q}}}$, then the graph $\Gamma /G$ is connected but may admit parallel edges, loops or semi-edges. Since the valence of every vertex in $\Gamma$ is 3, it follows that the vertices in $\Gamma /G$ have valence at most 3 and that $\lambda _G(x) \le 3$ for every dart x of $\Gamma /G$. Moreover, a labelled graph in ${{\mathcal {Q}}}$ can have at most 5 vertices (see Lemma 4.1). This shows that the set ${{\mathcal {Q}}}$ is a subset of the set ${{\mathcal {Q}}}^\circ$ of all connected subcubic labelled graphs $(Q,\lambda )$ on at most 5 vertices with $\lambda (x) \le 3$. The set ${{\mathcal {Q}}}^\circ$ is clearly finite, but still consists of an inconveniently large number of labelled graphs.

To determine which of the labelled graph in ${{\mathcal {Q}}}^\circ$ indeed arise as quotients of the cubic graphs in ${{\mathcal {G}}}$ by an appropriate cyclic group G (that is, which of them belong to ${{\mathcal {Q}}}$), we rely on the concept of a cyclic generalised voltage graph, first introduced in [25], and the associated generalised covering graph construction. Loosely speaking, this construction takes a labelled graph $(\Delta ,\lambda )$, together with an additional information, called voltage assignment $\zeta$, as an input and constructs a connected graph $\Gamma$ (called a cover, for short) having $(\Delta ,\lambda )$ as a labelled quotient. It was proved in [25] that as the voltage assignment $\zeta$ varies this procedure yields all possible connected graphs having $(\Delta ,\lambda )$ as a quotient by a cyclic group.

In Sect. 4, we use the results proved in [25] (and summarised in Sect. 3) to find a set of necessary conditions (see Theorem 4.2) for a labelled graph in ${{\mathcal {Q}}}^\circ$ to admit a connected vertex-transitive generalised cyclic cover belonging to ${{\mathcal {G}}}$. In Sect. 5 we determine, by means of forbidden labelled subgraphs, further necessary conditions for an element of ${{\mathcal {Q}}}^\circ$ to admit a cyclic generalised cover in ${{\mathcal {G}}}$ (see Theorem 5.9). The set of conditions given in Theorems 4.2 and 5.9 is restrictive enough to allow us to compute, via a brute-force algorithm, the subset ${{\mathcal {Q}}}^* \subseteq {{\mathcal {Q}}}^\circ$ of labelled graphs satisfying them. There are 20 such graphs.

In Sect. 6, we analyse the 20 labelled graphs of ${{\mathcal {Q}}}^*$ in detail, and show that precisely nine of them admit vertex-transitive cubic cyclic generalised covers belonging to ${{\mathcal {G}}}$ (see Fig. 2). These are the nine elements of the set ${{\mathcal {Q}}}$. However, due to some overlap in the families of covering graphs, only seven elements of ${{\mathcal {Q}}}$ are necessary to reconstruct ${{\mathcal {G}}}$. Finally in Sect. 7, we characterise the elements of ${{\mathcal {G}}}$ and complete the proof of Theorem 1.1.

Fig. 2

The nine labelled graphs in ${{\mathcal {Q}}}$, where darts with no label have $\lambda$-value 1. With the exception of the right-most graph, these graphs correspond to the 8 possible quotients of a k-multicirculant graph by a k-multicirculant automorphism, with $k \in \{1,2,3\}$

3 Covers

We now formally introduce the concept of a cyclic generalised voltage graph, which generalises voltage graphs (in the sense of [11]) for cyclic voltage groups, and is a special case of the wider class of generalised voltage graphs introduced in [26]. The definitions and results in this section are mostly taken from [25], where cyclic generalised voltage graphs were first defined. Each cyclic generalised voltage graph gives rise to a unique generalised covering graph (called covering graph for simplicity). By the end of the section, we characterise those cyclic generalised voltage graphs whose covering graphs are cubic (that is, connected, finite, simple 3-valent graphs).

Definition 3.1

Let $\Delta$ be a finite connected graph and let $\lambda :\textrm{D}(\Delta ) \rightarrow \mathbb {N}$, $\iota :\textrm{V}(\Delta ) \rightarrow \mathbb {N}$ and $\zeta :\textrm{D}(\Delta ) \rightarrow \mathbb {Z}$ be functions such that

$$\begin{aligned} \lambda (x)\iota (\mathop {\textrm{beg}}x)= & {} \lambda (x^{-1})\iota (\mathop {\textrm{beg}}x^{-1}), \end{aligned}$$

(3.1)

$$\begin{aligned} \zeta (x^{-1})\equiv & {} -\zeta (x) \quad (\hbox {mod}\, \lambda (x)\iota (\mathop {\textrm{beg}}x)) \end{aligned}$$

(3.2)

for every dart $x\in \textrm{D}(\Delta )$. Then, we say that the quadruple $(\Delta ,\lambda ,\iota ,\zeta )$ is a cyclic generalised voltage graph, and we call the functions $\lambda$, $\iota$ and $\zeta$ a labelling, an index function and a voltage assignment, respectively.

Definition 3.2

Let $(\Delta ,\lambda ,\iota ,\zeta )$ be a cyclic generalised voltage graph. The cover of $(\Delta ,\lambda ,\iota ,\zeta )$, denoted by $Cov(\Delta ,\lambda ,\iota ,\zeta )$ is the graph $\Gamma := (V',D',\mathop {\textrm{beg}}',\mathop {\textrm{inv}}')$ where:

• (1) $V' = \{(v,i) :v \in \textrm{V}(\Delta ), i \in \{0,\ldots ,\iota (v)-1\}\}$;

• (2) $D' = \{(x,i) :x \in \textrm{D}(\Delta ), i \in \{0,\ldots ,\lambda (x)\iota (\mathop {\textrm{beg}}x)-1\}\}$;

• (3) $\mathop {\textrm{beg}}' (x,i) = (\mathop {\textrm{beg}}x,i)$;

• (4) $(x,i)^{-1} = (x^{-1},i + \zeta (x))$.

Remark 3.3

Since the second coordinate of a vertex (v, i) or a dart (x, i) in the definition above is an element of $\{0,\ldots ,\iota (v)-1\}$ or $\{0,\ldots ,\lambda (x)\iota (\mathop {\textrm{beg}}x)-1\}$, respectively, any operation on the second coordinate is to be computed modulo $\iota (v)$ or $\lambda (x)\iota (\mathop {\textrm{beg}}x)$ accordingly. In particular, on the right-hand side of equality (4), the sum $i + \zeta (x)$ is to be computed modulo $\lambda (x)\iota (\mathop {\textrm{beg}}x)$.

Let $(\Delta ,\lambda ,\iota ,\zeta )$ be a cyclic generalised voltage graph and set $\Gamma = \textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$. For the sake of simplicity, we will write $v_i$ instead of (v, i) for a vertex of $\Gamma$, and $x_i$ instead of (x, i) for a dart of $\Gamma$. The natural projection $\pi : \Gamma \rightarrow \Delta$ that maps every $v_i \in \textrm{V}(\Gamma )$ to v and every $x_i \in \textrm{D}(\Gamma )$ to x is a graph epimorphism. For each vertex $v \in \textrm{V}(\Delta )$, we call the set $\pi ^{-1}(v)=\{v_i :i \in \{1,\ldots ,\iota (v)\}\}$ the fibre of v and we denote it $\hbox {fib}(v)$. Similarly, the fibre of a dart $x \in \textrm{D}(\Delta )$ is $\hbox {fib}(x)=\pi ^{-1}(x)=\{x_i :i \in \{0,\ldots ,\lambda (x)\iota (\mathop {\textrm{beg}}x)-1\}\}$.

Let $n= \hbox {lcm}\{\lambda (x)\iota (\mathop {\textrm{beg}}x) :x \in \textrm{D}(\Delta )\}$ and observe that the group $\mathbb {Z}_n$ acts on $\textrm{D}(\Gamma ) \cup \textrm{V}(\Gamma )$ by the rule $(z_i)^g=z_{i+g}$ for all $z_i \in \textrm{D}(\Gamma ) \cup \textrm{V}(\Gamma )$ and $g \in \mathbb {Z}_n$ (recall that the index $i+g$ is computed modulo $\iota (z)$, if $z \in \textrm{V}(\Gamma )$, or modulo $\lambda (z)\iota (\mathop {\textrm{beg}}z)$ if $z \in \textrm{D}(\Gamma )$). The permutation induced by each $g \in \mathbb {Z}_n$ is an automorphism of $\Gamma$ and the orbit of a dart (or a vertex) $z_i$ under this action is precisely $\hbox {fib}(z)$. Furthermore, the action of $\mathbb {Z}_n$ is faithful and hence there is an embedding $\phi :\mathbb {Z}_n \rightarrow \textrm{Aut}(\Gamma )$ (see [25, Lemma 6.3]). The image $\phi (\mathbb {Z}_n)$ is a cyclic group of order n generated by the automorphism of $\Gamma$ that maps every vertex $v_i \in \textrm{V}(\Gamma )$ to $v_{i+1}$ and every dart $x_i \in \textrm{D}(\Gamma )$ to $x_{i+1}$. We call this automorphism the canonical covering transformation of $\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ and we denote it by $\rho$.

In short, the covering graph $\Gamma$ admits a cyclic group of automorphisms of order n whose orbits on vertices and darts are precisely the fibres of vertices and darts of $(\Delta ,\lambda ,\iota ,\zeta )$.

Conversely, in view of [25, Theorem 5.3] and [25, Theorem 6.2] every graph admitting a cyclic subgroup of automorphism of order n is the cover of some cyclic generalised voltage graph $(\Delta ,\lambda ,\iota ,\zeta )$, and by [25, Lemma 6.1], it follows that $\hbox {lcm}\{\lambda (x)\iota (\mathop {\textrm{beg}}x) :x \in \textrm{D}(\Delta )\} = n$. Moreover, by [25, Theorem 6.6] we can always assume that $\zeta (x) = 0$ for all darts x lying on a prescribed spanning tree ${\mathcal {T}}$ of $\Delta$. A voltage assignment satisfying this condition is said to be ${\mathcal {T}}$-normalised. Let us summarise these observations in the following theorem:

Theorem 3.4

A graph $\Gamma$ admits a cyclic subgroup of automorphisms $G \le \textrm{Aut}(\Gamma )$ of order n if and only if $\Gamma \cong \textrm{Cov}(\Gamma /G, \lambda ,\iota ,\zeta )$ for some functions $\lambda$, $\iota$ and $\zeta$ where $\zeta$ is T-normalised for a spanning tree T of $\Gamma /G$ and $n= \hbox {lcm}\{\lambda (x)\iota (\mathop {\textrm{beg}}x) :x \in \textrm{D}(\Delta )\}$.

Fig. 3

A cyclic generalised voltage graph (bottom) along with its cyclic generalised cover (top)

Example 3.5

Consider the cyclic generalised voltage graph depicted in the bottom of Fig. 3. The function $\lambda$ is given in the figure as follows: each link has two numbers next to each of its endvertices, corresponding to the $\lambda$-values of each dart underlying this link; for instance, if we let x be the dart beginning at a and ending at b, then $\lambda (x) = 3$ and $\lambda (x^{-1})=1$. The semi-edge at c has a single label 1 and the loop at d has two labels, both equal to 1, corresponding to the $\lambda$-values of the darts underlying it. The voltage assignment is also given in the figure. The link joining a with b has an arrowhead directed from a to b with a 1 in boldface written above it. This indicates that the dart beginning at a and ending at b has voltage 1, while its inverse $x^{-1}$ has voltage $-1$. The semi-edge at c has voltage 3, as indicated by the boldface number above it. One dart underlying the loop at d has voltage 1 while its inverse has voltage $-1$. The values of $\iota$ are written below the graph. The graph at the top of Fig. 3 is then the cover of the cyclic generalised voltage graph.

Remark 3.6

Let $(\Delta ,\lambda ,\iota ,\zeta )$ be a cyclic generalised voltage graph and let $\Gamma = \textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$. Let $x \in \textrm{D}(\Delta )$ and $u = \mathop {\textrm{beg}}x$. Then, the following is straightforward from the definition of a cyclic generalised voltage graph:

• (1) $|\hbox {fib}(u)| = \iota (u)$;

• (2) $|\hbox {fib}(x)| = \lambda (x)\iota (u)$;

• (3) For every $u_i \in \hbox {fib}(u)$, there are exactly $\lambda (x)$ darts in $\hbox {fib}(x)$ that begin at $u_i$;

• (4) For every $u_i \in \hbox {fib}(u)$, $\deg (u_i) =\deg _{\lambda }(v)$, where

$$\begin{aligned} \deg _{\lambda }(v) = \sum \limits _{x \in \Delta (v)} \lambda (x). \end{aligned}$$

(3.3)

Since cubic graphs are the main object of study of this paper, we would like to focus precisely on those cyclic generalised voltage graphs whose covers are cubic graphs. Hence the following definition.

Definition 3.7

A cyclic generalised voltage graph $(\Delta ,\lambda ,\iota ,\zeta )$ is called a ccv-graph whenever $\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ is a cubic graph.

The following characterisation of ccv-graphs is a consequence of [25, Theorems 6.8 and 6.9].

Lemma 3.8

Let $(\Delta ,\lambda ,\iota ,\zeta )$ be a cyclic generalised voltage graph where $\zeta$ is ${\mathcal {T}}$-normalised for some spanning tree ${\mathcal {T}}$ of $\Delta$. Let $A = \{\zeta (x) :x \in \textrm{D}(\Delta )\}$ and $B = \{\iota (v) :x \in \textrm{V}(\Delta )\}$. Then, $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-graph if and only if all the following conditions are satisfied:

• (1) $\gcd (\lambda (x),\lambda (x^{-1})) = 1$ for all $x \in \textrm{D}(\Delta )$;

• (2) $\zeta (x) \not \equiv \zeta (y)$ $(\hbox {mod}\, \gcd (\iota (\mathop {\textrm{beg}}x), \iota (\mathop {\textrm{end}}x))$ for any two parallel darts $x,y \in \textrm{D}(\Delta )$;

• (3) $\zeta (x) \not \equiv 0$ $(\hbox {mod}\, \iota (\mathop {\textrm{beg}}x))$ for all darts x in a semi-edge;

• (4) $\gcd (A\cup B) = 1$;

• (5) $\deg _{\lambda }(v) = 3$ for all $v \in \textrm{V}(\Delta )$.

In the lemma above, conditions (1)–(3) are there to guarantee the covering graph $\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ is a simple graph, condition (4) that $\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ is connected, and condition (5), that it is 3-valent.

3.1 Extendability to ccv-Graphs

Let $\Delta$ be a connected finite graph, and let $\lambda : \textrm{D}(\Delta ) \rightarrow \mathbb {N}$ be an arbitrary function. We call the pair $(\Delta , \lambda )$ a labelled graph. Naturally, we obtain a labelled graph $(\Delta , \lambda )$ from every cyclic generalised voltage graph $(\Delta ,\lambda ,\iota ,\zeta )$ by simply disregarding the functions $\iota$ and $\zeta$. In this case, the fact that $\lambda$ comes from a generalised voltage graph, which by definition satisfies equality (3.1), restricts $\lambda$ to some degree. We say that a labelled graph $(\Delta ,\lambda )$ is extendable if there exist functions $\iota$ and $\zeta$ such that $(\Delta ,\lambda ,\iota ,\zeta )$ is a cyclic generalised voltage graph. We will be particularly interested in those extendable labelled graphs that can be extended to a ccv-graph.

A walk of length n is a sequence of darts $W=(x_1,x_2,\ldots ,x_n)$ such that $\mathop {\textrm{beg}}x_{i+1} = \mathop {\textrm{end}}x_i$ for all $i \in \{1,\ldots ,n-1\}$. We say W is closed if $\mathop {\textrm{end}}x_n = \mathop {\textrm{beg}}x_1$, and we say it is reduced if $x_{i+1} \ne x_i^{-1}$ for all $i \in \{1,\ldots ,n-1\}$. A path is a reduced walk where $\mathop {\textrm{beg}}x_i \ne \mathop {\textrm{beg}}x_j$ for all $i \ne j$ and a cycle is a closed path. A cycle of length n is also called an n-cycle. A tree is a connected graph without any cycles.

For a walk $W=(x_1,x_2,\ldots ,x_n)$, we define the inverse of W as the walk $W^{-1}=(x_n^{-1},x_{n-1}^{-1},\ldots ,x_1^{-1})$. If $W_1=(x_1,x_2,\ldots ,x_n)$ and $W_2=(y_1,y_2,\ldots ,y_m)$ are two walks such that $\mathop {\textrm{end}}x_n = \mathop {\textrm{beg}}y_1$, then we define the concatenation of $W_1$ and $W_2$ as $W_1W_2 = (x_1,\ldots ,x_n,y_1,\ldots ,y_m)$.

Let $(\Delta ,\lambda )$ be a labelled graph. We can extend the labelling $\lambda$ to a function $\lambda ^*$ that assigns to each walk of $\Delta$ a rational number. For a walk $W=(x_1,x_2,\ldots ,x_n)$ in $\Delta$, we let

$$\begin{aligned} \lambda ^*(W) := \prod \limits _{i=1}^n \frac{\lambda (x_i)}{\lambda (x_i^{-1})}. \end{aligned}$$

(3.4)

We then have that

$$\begin{aligned} \lambda ^*(W^{-1}) = \lambda ^*(W)^{-1} \text { and } \lambda ^*(W_1W_2)= \lambda ^*(W_1)\lambda ^*(W_2) \end{aligned}$$

(3.5)

for any two walks $W_1$ and $W_2$ for which the concatenation is defined. The following is a useful characterisation of labelled graphs that are extendable.

Lemma 3.9

[25, Lemma 3.5] A labelled graph $(\Delta ,\lambda )$ is extendable if and only if $\lambda ^*(C)=1$ for every closed walk C of $\Delta$.

Naturally, not every extendable labelled graph $(\Delta ,\lambda )$ can be extended to a ccv-graph. However, if $(\Delta ,\lambda )$ does extend to a ccv-graph $(\Delta ,\lambda ,\iota ,\zeta )$, we say $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-extension of $(\Delta ,\lambda )$ and we call the covering graph $\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ a ccv-cover of $(\Delta ,\lambda )$.

Lemma 3.10

[25, Proposition 7.1] A connected labelled graph $(\Delta ,\lambda )$ can be extended to a ccv-graph if and only if the following holds:

• (1) $(\Delta ,\lambda )$ is extendable;

• (2) $\lambda (x)=\lambda (x^{-1})$ implies $\lambda (x)=1$;

• (3) $\lambda (x) = \lambda (y) = 1$ for any two parallel darts x and y;

• (4) $\lambda (x) = 1$ for every dart x underlying a semi-edge;

• (5) $\deg _{\lambda }(v) = 3$ for all vertices $v \in \textrm{V}(\Delta )$.

Let $(\Delta , \lambda )$ be a labelled graph and let $x \in \textrm{D}(\Delta )$ be such that $x \ne x^{-1}$ and $\lambda (x) \le \lambda (x^{-1})$. We say $\{x,x^{-1}\}$ is an edge of type $[\lambda (x),\lambda (x^{-1})]$, or simply a $[\lambda (x),\lambda (x^{-1})]$-edge. From Lemma 3.10, we see that if $(\Delta , \lambda )$ is extendable to a ccv-graph, then the edges of $\Delta$ are all of type [1, 1], [1, 2], [1, 3] or [2, 3] (see also [25, Corollary 7.2]).

Now, suppose $\lambda (x) = 1$ for all $x \in \textrm{D}(\Delta )$. That is, every edge of $(\Delta , \lambda )$ is a [1, 1]-edge. By Lemmas 3.9 and 3.10, $(\Delta , \lambda )$ admits a ccv-extension of $(\Delta ,\lambda ,\iota ,\zeta )$ and a ccv-cover $\Gamma := \textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$. Since $\lambda (x) = 1$ for all $x \in \textrm{D}(\Delta )$, it follows from formula (3.1) and the connectedness of $\Delta$ that $\iota (v) = \iota (u)$ for any two vertices u and v of $\Delta$. Then, the canonical covering transformation $\rho$ of $\Gamma$ (mapping every vertex $v_i \in \textrm{V}(\Gamma )$ to $v_{i+1}$) is a semiregular automorphism. Its vertex orbits are precisely the vertex fibres of $\Gamma$. Therefore, if $\Delta$ has k vertices, then $\rho$ has k orbits on vertices and $\Gamma$ is a k-multicirculant graph (Fig. 4).

3.2 Simplified Voltages

Fig. 4

A Möbius ladder, the cube graph and $K_{3,3}$ as covers of ccv-graphs (where the voltage is simplified)

As one would expect, for given a labelled graph $(\Delta ,\lambda )$, there may exist different ccv-extensions $(\Delta ,\lambda ,\iota ,\zeta )$ and $(\Delta ,\lambda ,\iota ,\zeta ')$ such that $\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta ) \cong \textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta ')$. It would be convenient to take, among all the possible ccv-extensions yielding isomorphic covers, one with a voltage assignment that is as ‘nice’ as possible. As was proved in [25, Lemma 7.4], for every ccv-extension $(\Delta ,\lambda ,\iota ,\zeta )$ of a labelled graph $(\Delta ,\lambda )$ there exists a voltage assignment $\zeta '$ that is simplified in the sense of Definition 3.11, such that $\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta ) \cong \textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta ')$.

Definition 3.11

Let $(\Delta ,\lambda ,\iota ,\zeta )$ be a ccv-graph. The voltage $\zeta$ is a simplified voltage if for all $x \in \textrm{D}(\Gamma )$ the following holds:

• (1) $\zeta$ is ${\mathcal {T}}$-normalised for a spanning tree ${\mathcal {T}}$ containing all [i, j]-edges with $i \ne j$;

• (2) $\zeta (x) < \gcd ( \iota (\mathop {\textrm{beg}}x), \iota (\mathop {\textrm{beg}}x^{-1}))$;

• (3) $\zeta (x) = \iota (\mathop {\textrm{beg}}x)/2$ whenever x underlies a semi-edge;

• (4) $0 < \zeta (x)$ and $\zeta (x) \ne \iota (\mathop {\textrm{beg}}x)/2$ whenever x underlies a loop.

Note that if we assume a voltage $\zeta$ satisfies (1) in the definition above, then item (2) is equivalent to

• (2’) $\zeta (x) < \iota (\mathop {\textrm{beg}}x)$.

Indeed, clearly, (2) implies (2’). Suppose $\zeta$ satisfies (1) and (2’). If for some $x \in \textrm{D}(\Gamma )$ we have $\zeta (x) = 0$, then $\zeta (x) < \iota (\mathop {\textrm{beg}}x)$. If $\zeta (x) \ne 0$, then by (1) we have $\iota (\mathop {\textrm{beg}}x) = \iota (\mathop {\textrm{beg}}x^{-1})$ and thus $\gcd ( \iota (\mathop {\textrm{beg}}x), \iota (\mathop {\textrm{beg}}x^{-1})) = \iota (\mathop {\textrm{beg}}x)$. Then, $\zeta (x) < \iota (\mathop {\textrm{beg}}x)=\gcd ( \iota (\mathop {\textrm{beg}}x), \iota (\mathop {\textrm{beg}}x^{-1}))$ and (2) holds.

Remark 3.12

One of the advantages of considering ccv-graphs with simplified voltage assignments is that the adjacency rules for the corresponding covering graphs become quite straightforward. Indeed, suppose $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-graph where $\zeta$ is simplified. Let $x \in \textrm{D}(\Delta )$, let $u = \mathop {\textrm{beg}}x$ and $v = \mathop {\textrm{end}}x$, and let $e = \{x,x^{-1}\}$. Then, for all $u_i \in \hbox {fib}(u)$ we have:

• (1) If $u \ne v$ and e is a [1, 1]-edge, then $u_i \sim v_{i + \zeta (x)}$;

• (2) If $u \ne v$ and e is a [1, j]-edge, $j \ne 1$, then $u_{i + k\cdot \iota (v)} \sim v_i$, with $0 \le k < j$;

• (3) If $u = v$ and e is a loop, then $u_i \sim u_{i+\zeta (x)}$ and $u_i \sim u_{i-\zeta (x)}$;

• (4) If e is a semi-edge, then $u_i \sim u_{i+(\iota (u)/2)}$.

Let $(\Delta ,\lambda ,\iota ,\zeta )$ be a ccv-graph. By [25, Proposition 7.4] there exists a simplified voltage assignment $\zeta '$ for $\Delta$ such that $\textrm{Cov}(\Delta , \lambda ,\iota ,\zeta ) \cong \textrm{Cov}(\Delta , \lambda ,\iota ,\zeta ')$. This implies that every cubic graph is the cover of a ccv-graph with a simplified voltage assignment. For this reason, we will henceforth always assume that the voltage of a ccv-graph is simplified. The following theorem summarises the contents of this section.

Theorem 3.13

A graph $\Gamma$ is cubic and admits a cyclic group of automorphisms of order n if and only if it is the cover of a cyclic generalised voltage graph $(\Delta ,\lambda ,\iota ,\zeta )$ where $\lambda : \textrm{D}(\Delta ) \rightarrow \{1,2,3\}$ satisfies conditions (1)–(4) of Lemma 3.10, $\zeta$ is simplified, $\gcd \{\zeta (x),\iota (v) :x \in \textrm{D}(\Delta ), v \in \textrm{V}(\Delta )\}=1$ and $\hbox {lcm}\{\lambda (x)\iota (\mathop {\textrm{beg}}x) :x \in \textrm{D}(\Delta )\}=n$.

4 Vertex-Transitive Covers

We have shown in Sect. 3 that if $\Gamma$ is a cubic graph admitting a cyclic group of automorphisms G, then $\Gamma$ is isomorphic to a ccv-cover of some labelled graph $(\Delta ,\lambda )$, where the labelling $\lambda$ satisfies conditions (1)–(5) of Lemma 3.10; that is, $(\Delta ,\lambda )$ is extendable, $\lambda (x)=1$ for every dart x underlying a loop, a semi-edge or a link that is parallel to another link, and $\deg _{\lambda }(x)=3$ for all darts $x \in \textrm{D}(\Delta )$. If in addition we suppose that $\Gamma$ is vertex-transitive and that G has order at least $\textrm{V}(\Gamma )/3$, then further restrictions are set on the labelled graph $(\Delta ,\lambda )$. It was shown in [27] that if $\Gamma$ is a cubic vertex-transitive graph and $G \le \textrm{Aut}(\Gamma )$ is cyclic, then the number of orbits of G is bounded by a function of $k=|\textrm{V}(\Gamma )|/|G|$. This, in turn, bounds the number of vertices of the quotient $\Gamma /G$. Furthermore, the ratio between the sizes of the largest and smallest orbits of G is also bounded, which restricts the labelling $\lambda$. Let us be more precise.

Let $\Gamma$ be a cubic graph of order $n > 20$ admitting a cyclic subgroup of automorphisms G. Then, $\Gamma$ is isomorphic to the cover of some ccv-graph $(\Delta ,\lambda ,\iota ,\zeta )$ where $\hbox {lcm}\{\lambda (x)\iota (\mathop {\textrm{beg}}x):x \in \textrm{D}(\Delta ) \}=|G|$. We can slightly abuse the language and identify $\Gamma$ with $\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$. Suppose $\Gamma$ is vertex-transitive and let $m = |G|$. Then, by [27, Theorem 4.7], a G-orbit on vertices must have size m/i for some $i \in \{1,2,3,4,6\}$ and the largest G-orbit has size precisely m. It follows that for any two vertices ${\bar{u}}$ and ${\bar{v}}$ of $\Gamma$, we have

$$\begin{aligned} \frac{1}{6}|{\bar{u}}^G| \le |{\bar{v}}^G| \le 6|{\bar{u}}^G|. \end{aligned}$$

Since the orbits of G on $\textrm{V}(\Gamma )$ are identified with the fibres of $\textrm{V}(\Delta )$ we see that

$$\begin{aligned} \frac{1}{6}\iota (u) \le \iota (v) \le 6\cdot \iota (u) \end{aligned}$$

(4.1)

for any two $u,v \in \textrm{V}(\Delta )$ (recall that $\iota (u) = |\hbox {fib}(u)|$ for all $u \in \textrm{V}(\Delta )$). If in addition we suppose that $m \ge n/3$, then there must exist a vertex ${\hat{u}} \in \textrm{V}(\Delta )$ such that

$$\begin{aligned} 3 \cdot \iota ({\hat{u}}) \ge \sum \limits _{v \in \textrm{V}(\Delta )} \iota (v) = |\textrm{V}(\Gamma )|. \end{aligned}$$

(4.2)

Furthermore, [27, Theorem 1.6] asserts that if $\Gamma$ has order $n>20$ and ${\bar{u}} \in \Gamma$ is such that ${\bar{u}}^G$ is of maximal order among all G-orbits, then ${\bar{u}}$ has a neighbour ${\bar{v}}$ such that ${\bar{u}}^G \ne {\bar{v}}^G$ but $|{\bar{u}}^G| = |{\bar{v}}^G|$. In particular, since the largest orbit of G has size at least n/3, this implies that at least two thirds of the vertices of $\Gamma$ are contained in only two orbits (${\bar{u}}^G$ and ${\bar{v}}^G$). It is an easy exercise to see that the remaining vertices can be divided in, at most, 3 different orbits (of size n/9 each, or all three having different sizes: n/6, n/9 and n/18). Hence, we obtain the following lemma.

Lemma 4.1

Let $\Gamma$ be a cubic vertex-transitive graph of order $n > 20$, and let $G \le \textrm{Aut}(\Gamma )$ be a cyclic group with an orbit of size n/3 or greater. Then, G has at most 5 orbits on vertices.

Now, consider the function $\lambda ^*$ defined with formula (3.4). If $W=(x_1,x_2,\ldots ,x_n)$ is a uv-walk in $\Delta$, then by a consecutive application of equality (3.1) to the darts of W we have

$$\begin{aligned} \iota (v) = \lambda ^*(W)\iota (u). \end{aligned}$$

(4.3)

Since u and v are arbitrary vertices, we see that the index function $\iota$ is completely determined by the labelling $\lambda$ (as $\lambda ^*$ depends only on $\lambda$) and the value of $\iota$ on a single vertex. The following theorem sums up the preceding paragraphs.

Theorem 4.2

Let $(\Delta ,\lambda )$ be a labelled graph, let $\Gamma$ be a ccv-cover of $(\Delta ,\lambda )$ of order $n>20$ and let T be a spanning tree of $\Delta$. If $\Gamma$ is vertex-transitive and admits an automorphism of order $m \ge \frac{n}{3}$, then the following holds:

• (1) $(\Delta ,\lambda )$ is extendable;

• (2) $\deg _{\lambda }(v) = 3$ for all vertices $v \in \textrm{V}(\Delta )$;

• (3) $\lambda (x)=\lambda (x^{-1})$ implies $\lambda (x)=1$;

• (4) $\lambda (x) = \lambda (y) = 1$ for any two parallel darts x and y;

• (5) $\lambda (x) = 1$ for every dart x underlying a semi-edge;

• (6) $\Delta$ has at most 5 vertices;

moreover, there exists a vertex ${\hat{u}} \in \textrm{V}(\Delta )$ such that:

• (7) ${\hat{u}}$ is incident to an edge of type [1, 1];

• (8) $\frac{1}{6} \le \lambda ^*(W_v)$;

• (9) $\sum \limits _{v \in \textrm{V}(\Delta )\setminus \{{\hat{u}}\}} \lambda ^*(W_v) \le 2$;

for every $v \in \textrm{V}(\Delta )\setminus \{{\hat{u}}\}$, where $W_v$ denotes the unique ${\hat{u}}v$-path in T.

Proof

That items (1)–(5) hold follows at once from Lemma 3.10. Item (6) holds by Lemma 4.1. Now, let $u \in \textrm{V}(\Gamma )$ be such that $|u^G|$ has maximum cardinality amongst all the vertex orbits of G. Then, $|u^G| \ge \frac{n}{3}$. Let ${\hat{u}}=\pi (u)$ and let $v \in \textrm{V}(\Delta ){\setminus }\{{\hat{u}}\}$ (recall that the natural projection $\pi$ maps every vertex $v_i \in \hbox {fib}(v)$ to v). That ${\hat{u}}$ is incident to a [1, 1]-edge follows from [27, Theorem 4.7], and thus (7) holds. Furthermore, by (4.1) we have $\frac{1}{6}\iota ({\hat{u}}) \le \iota (v)$, but by (4.3) we can replace $\iota (v)$ by $\lambda ^*(W_v)\iota ({\hat{u}})$. Thus (8) holds. To see that (9) holds, subtract $\iota ({\hat{u}})$ on both sides of inequality (4.2) and replace $\iota (v)$ by $\lambda ^*(W_v)\iota ({\hat{u}})$. $\square$

5 Artefacts

A labelled subgraph of a labelled graph $(\Delta ,\lambda )$ is a pair $(\Delta ',\lambda ')$ where $\Delta '$ is a subgraph of $\Delta$ and $\lambda '$ is the restriction $\lambda \mid _{\textrm{D}(\Delta ')}$. In this section, we will define a set of ‘forbidden subgraph’ for a labelled graph, that we call artefacts. An artefact in a labelled graph $(\Delta , \lambda )$ is a labelled subgraph of $(\Delta , \lambda )$ that guaranties the existence of a particular subgraph (containing a short cycle) in any ccv-cover of $(\Delta , \lambda )$. We will show that a labelled graph containing certain artefacts cannot admit a vertex-transitive ccv-cover of order larger than 10. First, we will define the notion of the signature of a graph.

Let $\Gamma$ be a cubic graph, let x be a dart of $\Gamma$ and c be a positive integer. Denote by $\epsilon _c(x)$ the number of c-cycles (cycles of length c) that pass through x. Let $v \in \textrm{V}(\Gamma )$ and let $\{x_1,x_2,x_3\}$ be the set of darts beginning at v, ordered in such a way that $\epsilon _c(x_1) \le \epsilon _c(x_2) \le \epsilon _c(x_3)$. The triplet $(\epsilon _c(x_1),\epsilon _c(x_2),\epsilon _c(x_3))$ is then called the c-signature of v. Informally, the c-signature of v tells us how the cycles of length c passing through v are distributed among the darts incident to v. If all vertices of $\Gamma$ have the same c-signature, we say that $\Gamma$ is c-cycle-regular, and we say the c-signature of $\Gamma$ is the c-signature of any of its vertices. Observe that if $\Gamma$ is vertex-transitive, then $\Gamma$ is c-cycle-regular for all $c \in \mathbb {N}$. For cubic graphs of small girth g, the g-signature is sometimes enough to completely determine the graph. The following lemma is a direct consequence of the results proved in [28] (or independently in [8]) and [29], where a g-cycle-regular graph, where g is the girth of the graph, is called girth-regular.

Lemma 5.1

(See [28, Theorem 1.5] and [29, Theorem 1].) Let $\Gamma$ be a cubic girth-regular graph of girth $g \le 6$. Then, either the g-signature of $\Gamma$ is (0, 1, 1) or one of the following occurs:

• (1) $g=3$ and $\Gamma \cong K_4$;

• (2) $g=4$ and one the following occurs

  • (a) $\Gamma$ has signature (1, 2, 2) and is isomorphic to a prism or a Möbius ladder;

  • (b) $\Gamma$ is isomorphic to $K_{3,3}$ or the cube graph $Q_3$;

• (3) $g=5$ and $\Gamma$ is isomorphic to the Petersen graph or the dodecahedron $\textrm{GP}(10,2)$.

• (4) $g=6$ and one of the following occurs:

  • (a) $\Gamma$ belongs to a finite list of exceptional graphs with at most 20 vertices;

  • (b) $\Gamma$ has signature (1, 1, 2), (2, 2, 2) or (3, 4, 5);

  • (c) $\Gamma$ has signature (2, 3, 3) and is isomorphic either to

    • a cyclic Haar graph $\textrm{H}(3m;k,m)$ of order $6\,m$, $m>3$, where $k=1$ if $m \equiv 0\> (\hbox {mod}\, 3)$ and $k=3$ otherwise;

    • a graph $\textrm{SDW}(m,3)$ of order $6\,m$, $m>3$.

Remark 5.2

The Haar graph $\textrm{H}(3m;k,m)$ featuring in part (c) of the case $g=6$ of Lemma 5.1 was defined in [29, Sect. 2.4] as the bipartite Cayley graphs on the dihedral group $D_{3\,m} = \langle \rho , \tau \mid \rho ^{3\,m}, \tau ^2, (\rho \tau )^2\rangle$ with respect to the connection set $\{\tau , \tau \rho ^k, \tau \rho ^m\}$ and were denoted by $\Delta _m$. It is, however, clear that such defined graph $\Delta _m$ and the cyclic Haar graph $\textrm{H}(3m;k,m)$ are isomorphic. As was proved there, their automorphism group has order 6m and thus acts regularly on the vertices.

Similarly, the graph $\textrm{SDW}(m,3)$ was denoted in [29] as $\Sigma _m$ and defined as the Cayley graph on the group $D_m\times \mathbb {Z}_3$ with respect to the connection set $S=\{(\rho \tau ,0),(\tau ,1), (\tau ,2)\})$, where $D_m = \langle \rho , \tau \mid \rho ^m, \tau ^2, (\rho \tau )^2\rangle$ denotes the dihedral group of order 2m. To prove that $\Sigma _m$ is indeed isomorphic to $\textrm{SDW}(m,3)$ one can check that the mapping $(\rho ^i\tau ^j,k) \mapsto (i,k,1-j)$ is indeed a graph isomorphism. As was proved in [29, Proposition 5], the automorphism group of $\textrm{SDW}(m,3)$, $m>3$, is isomorphic to the group $S_3 \times D_m$ (where by $S_3$ we denote the symmetric group of order 6).

Corollary 5.3

If $\Gamma$ is a cubic arc-transitive graph of girth smaller than 6, then $\Gamma$ is isomorphic to one of the following: $K_4$, $K_{3,3}$, the three-dimensional cube $Q_3$, the Petersen graph or the dodecahedron $\textrm{GP}(10,2)$.

Lemma 5.4

[21, Lemma 4.2] If $\Gamma$ is a cubic arc-transitive graph of girth 6, then either $\Gamma$ has 6-signature (2, 2, 2) or it has order $n \le 20$.

Lemma 5.5

Let $(\Delta , \lambda ,\iota ,\zeta )$ be a ccv-graph and suppose $\Gamma := \textrm{Cov}(\Delta , \lambda ,\iota ,\zeta )$ is vertex-transitive. If for some $x \in \textrm{D}(\Delta )$ we have $\lambda (x)=3$, then $\Gamma$ is arc-transitive.

Proof

Let $u = \mathop {\textrm{beg}}x$ and $u_0 \in \hbox {fib}(u)$. Let a and b be two arbitrary darts of $\Gamma$. Since $\Gamma$ is vertex-transitive, there exist automorphisms $\phi ,\psi \in \textrm{Aut}(\Gamma )$ such that $(\mathop {\textrm{beg}}a)^{\phi }=u_0=(\mathop {\textrm{beg}}b)^{\psi }$. In particular, both $a^{\phi }$ and $b^{\psi }$ begin at $u_0$. Furthermore, since $\lambda (x)=3$, all three darts beginning at $u_0$ belong to the same orbit of the cyclic group of automorphisms of $\Gamma$ preserving the fibres, and thus there exists $\gamma \in \textrm{Aut}(\Gamma )$ such that $a^{\phi \gamma } = b^{\psi }$. Then, $a^{\phi \gamma \psi ^{-1}}=b$. We conclude $\Gamma$ is arc-transitive. $\square$

Let $A_1$, $A_2$, $A_3$, $A_4$ and $A_5$ be the 5 labelled graphs depicted in the bottom row of Fig. 5.

Fig. 5

The five artefacts $A_i$ with $i \in \{1,2,3,4,5\}$ (bottom row). Above each, a small subgraph of the cover of any ccv-graph containing $A_i$

Lemma 5.6

Let $(\Delta ,\lambda )$ be a labelled graph and let $\Gamma$ be a ccv-cover of $(\Delta ,\lambda )$. Suppose $(\Delta ,\lambda )$ contains an artefact $A_j$ for some $j \in \{1,2,3,4,5\}$. Then:

• (1) if $j=1$, $\Gamma$ contains a 3-cycle;

• (2) if $j \in \{2,3\}$, $\Gamma$ contains a 4-cycle;

• (3) if $j \in \{4,5\}$, $\Gamma$ contains a copy of $K_{3,2}$.

Proof

The proof consists in repeatedly applying Remark 3.12 for each of the five possible cases. For instance, suppose $\Gamma \cong \textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ where $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-extension of $(\Delta ,\lambda )$ and that $(\Delta ,\lambda )$ contains a subgraph isomorphic to $A_j$ for some $j \in \{1,\ldots ,5\}$. Recall that we may assume that [a, b]-edges with $a \ne b$ have trivial voltage and that the voltage of a semi-edge x is $\iota (\mathop {\textrm{beg}}x)/2$. Assume the notation of Fig. 5.

First suppose $j = 1$. Then, $\iota (u)=2\cdot \iota (v)=2\,m$ for some $m \in \mathbb {N}$ and since uv is a [1, 2]-edge, it follows from Remark 3.12 that each $v_i \in \hbox {fib}(v)$ is adjacent to $u_i$ and $u_{i+m}$. Furthermore, since u is incident to a semi-edge, $u_i$ is incident to $u_{i+m}$ (again, by Remark 3.12). Then, $(u_i,u_{i+m},v_i)$ is a 3-cycle of $\Gamma$ for all $i \in \{0,\ldots ,m-1\}$.

Now, suppose $j = 2$. Since uw and uv are [1, 2]-edges, $\iota (u) = 2m$ for some m, and by Remark 3.12, each $v_i \in \hbox {fib}(v)$ and $w_i \in \hbox {fib}(w)$ is adjacent to both $u_i$ and $u_{i+m}$. It follows that $(u_i, w_i, u_{i+m}, v_i)$ is a 4-cycle of $\Gamma$ for all $i \in \{0,\ldots ,m-1\}$.

If $j=3$, then $\iota (u) = 2m$ for some m since u is incident to a semi-edge. Moreover, since uv is a [1, 1]-edge we have $\iota (u)=\iota (v)$, and the dart x, beginning at u and ending at v, may have non-trivial voltage $\zeta (x)$. By Remark 3.12, each $u_i \in \hbox {fib}(u)$ is adjacent to $v_{i+\zeta (x)}$. Since both u and v are adjacent to a semi-edge, we have that $u_i \sim u_{i+m}$ and $v_i \sim v_{i+m}$ for all $i \in \{0,\ldots ,m-1\}$. Therefore, $(u_i,v_{i+\zeta (x)}, v_{i+m+\zeta (x)}, u_{i+m})$ is a 4-cycle in $\Gamma$.

The two remaining cases follow in a similar way from Remark 3.12. $\square$

Corollary 5.7

Let $(\Delta ,\lambda )$ be labelled graph containing an artefact $A_i$ with $i \in \{1,2,3,4,5\}$ and a dart x such that $\lambda (x)=3$. If $\Gamma$ is a vertex-transitive ccv-cover of $(\Gamma ,\lambda )$, then $\Gamma$ is isomorphic to $K_4$, $K_{3,3}$ or $Q_3$.

Proof

By Lemma 5.5$\Gamma$ is arc-transitive and since it contains an artefact $A_i$ with $i \in \{1,2,3,4,5\}$ it has girth 3 or 4. It follows from Corollary 5.3 that $\Gamma$ is isomorphic to $K_4$, $K_{3,3}$ or $Q_3$. $\square$

Let $A_6$ and $A_7$ be the labelled graphs depicted in the bottom row of Fig. 6.

Fig. 6

The two artefacts $A_6$ and $A_7$ (bottom row). Above each, a small subgraph of the cover of any ccv-graph containing it

Lemma 5.8

If $(\Delta ,\lambda )$ is a labelled graph containing $A_6$ or $A_7$, then no ccv-cover of $(\Delta ,\lambda )$ is vertex-transitive.

Proof

Let $(\Delta ,\lambda ,\iota ,\zeta )$ be a ccv-extension of $(\Delta ,\lambda )$ such that $\Gamma \cong \textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$. Suppose, on the contrary, that $\Gamma$ is vertex-transitive and $(\Delta ,\lambda )$ contains a copy of $A_j$ for some $j \in \{6,7\}$.

Now, suppose $j=7$. Let a, b, c and d be the vertices of $A_7$, as they are labelled in Fig. 6. There are two edges connecting b to a. Without loss of generality, we may assume the darts on one of these edges have trivial voltage, as necessarily one of these edges must lie on a spanning tree of $\Delta$ and (we can assume) the voltage assignment $\zeta$ is simplified. As for the other edge, let $r \ne 0$ be the voltage of the dart underlying it and beginning at b (and thus, its inverse, beginning at a, has voltage $-r$). Let $\iota (c)=m$ so that $\iota (b)=\iota (a)=2m$. Observe that $(c_0,b_0,a_0,a_m,b_m)$ and $(c_0,b_0,a_{r},a_{m+r},b_m)$ are 5-cycles of $\Gamma$ (note that this is true even if $r=m$). Then, every dart beginning at $b_0$ lies on a 5-cycle. Since dc is a [1, i]-edge of $(\Delta ,\lambda )$, we see that $d_0$ is adjacent to $c_0$ in $\Gamma$. Furthermore, since $\Gamma$ is vertex-transitive, the dart beginning at $d_0$ and ending at $c_0$ lies on a 5-cycle $C:=(d_0,c_0,u,v,w)$, for some $u,v,w \in \textrm{V}(\Gamma )$. Clearly, $u \in \{b_0,b_m\}$ and $v \in \{a_0,a_r,a_m,a_{m+r}\}$, since both $\hbox {fib}(c)$ and $\hbox {fib}(b)$ are independent sets. Then, $w \in \hbox {fib}(a)\cup \hbox {fib}(b)$ which leads us to a contradiction, since no vertex in $\hbox {fib}(a)\cup \hbox {fib}(b)$ is adjacent to a vertex in $\hbox {fib}(d)$. Therefore, there is no 5-cycle tracing the edge $d_0c_0$ and thus $\Gamma$ is not vertex-transitive.

Finally, suppose $j=6$ and assume the notation in Fig. 6. Then, $\iota (d) = m$ for some $m \in \mathbb {N}$. By Lemma 5.6, $\Gamma$ contains a 3-cycle and thus the vertex $d_0 \in \hbox {fib}(d)$ must lie on a 3-cycle C. Since $d_0$ has two neighbours in $\hbox {fib}(c)$, one vertex of C must be in $\hbox {fib}(c)$. Without loss of generality, let $c_0$ be that vertex. Then, the third vertex in C must be a common neighbour of $d_0$ and $c_0$, but the other two neighbours of $c_0$ are $b_0$ and $b_{2m}$, none of which si adjacent to $d_0$. Therefore, $d_0$ does not lie on a 3-cycle, and $\Gamma$ is not vertex-transitive. $\square$

The following theorem, which is a consequence of Corollary 5.7 and Lemma 5.8, summarises the contents of this section.

Theorem 5.9

Let $(\Delta ,\lambda )$ be a labelled graph and let $\Gamma$ be a ccv-cover of $(\Delta ,\lambda )$ with more than 20 vertices. If $\Gamma$ is vertex-transitive, then one of the following holds:

• (1) $(\Delta ,\lambda )$ does not contain an artefact $A_i$ with $i \in \{1,2,3,4,5\}$ and a dart x such that $\lambda (x)=3$;

• (2) $(\Delta ,\lambda )$ does not contain an artefact $A_i$ with $i \in \{6,7\}$.

6 The Set ${{\mathcal {Q}}}$

Recall that ${{\mathcal {G}}}$ is the set of all vertex-transitive cubic graphs $\Gamma$ of order $n>20$ admitting an automorphism g of order n/3 or greater, and that ${{\mathcal {Q}}}$ is the set of all labelled quotients $\Gamma / \langle g \rangle$. As a step towards proving Theorem 1.1, we must determine the set ${{\mathcal {Q}}}$. Then, we can reconstruct ${{\mathcal {G}}}$ by considering all vertex-transitive ccv-covers of elements of ${{\mathcal {Q}}}$. Observe that ${{\mathcal {Q}}}$ is a subset of the set ${{\mathcal {Q}}}^*$ of all labelled graphs satisfying the conditions stated in Theorems 4.2 and 5.9. These conditions are restrictive enough to allow us to quickly compute ${{\mathcal {Q}}}^*$ by means of a brute-force algorithm. As it transpires, ${{\mathcal {Q}}}^*$ consist of 20 labelled graphs. To determine ${{\mathcal {Q}}}$ it suffices to determine which of these graphs admit a vertex-transitive ccv-cover with more than 20 vertices.

The eight elements of ${{\mathcal {Q}}}^*$ having less than four vertices, shown in Fig. 7, correspond to the eight possible quotients of a cubic graph by a $(k,\ell )$-semiregular automorphism with $k \in \{1,2,3\}$.

Each of these eight graphs admits at least one vertex-transitive ccv-cover with more than 20 vertices (see [25, Theorem 1.1] or [22] and [24] for details). Therefore, the eight graphs of Fig. 7 are elements of ${{\mathcal {Q}}}$.

Fig. 7

Elements of ${{\mathcal {Q}}}^*$ with at most 3 vertices

The remaining 12 labelled graphs of ${{\mathcal {Q}}}^*$ are shown in Fig. 8. We will show that, with the exception of $\Delta _{12}$, none of these graphs admit a vertex-transitive ccv-cover of order larger than 20. The graph $\Delta _{12}$ will be studied in detail in Sect. 6.1.

Now consider a labelled graph $\Delta _i$ from Fig. 8 and suppose $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-extension of $\Delta _i$. We may assume that $\zeta$ is a simplified voltage assignment and agrees with Fig. 8, where we adopt the same notation convention as in Example 3.5, which we revisit here for convenience. For a symbol $\alpha \in \{r,s\}$, an edge with an arrow oriented from, say, u to v, with the letter $\alpha$ next to it, indicates that the dart x underlying this edge and beginning at u has voltage $\alpha$, for some $0 \le \alpha < \iota (v)$. A loop with the letter $\alpha$ next to it, indicates that one of the underlying darts, say x, has voltage $\alpha$ for some integer $0< \alpha < \iota (\mathop {\textrm{beg}}x)$. For a semi-edge x, $\zeta (x) = \iota (\mathop {\textrm{beg}}x)/2$. All other darts belong to a spanning ${\mathcal {T}}$ and have trivial voltage. The vertices of each $\Delta _i$ are named in Fig. 8, but we refrain from naming the darts in the figure so as not to overburden it. Since parallel darts in a ccv-graph need to have distinct voltages, every dart in $\Delta _i$ is completely determined by its endpoints along with its voltage. Hence, we will denote a dart x of $\Delta _i$ beginning at u and ending at v by $(uv)_{\zeta (x)}$; its inverse is then $(vu)_{-\zeta (x)}$. As every cover of a ccv-graph is a simple graph, the darts in the fibre of $(uv)_{\zeta (x)}$ are denoted by $u_iv_{i+\zeta }$ for $i \in \{0,\ldots ,\iota (u)-1\}$ (like arc or directed edges are usually denoted).

Fig. 8

Elements of ${{\mathcal {Q}}}^*$ with more than 3 vertices

Let $(\Delta ,\lambda )$ be a labelled graph, $\Gamma$ be a ccv-cover of $(\Delta ,\lambda )$ and let $\pi : \Gamma \rightarrow \Delta$ be the corresponding projection. If W is a uv-walk in $\Delta$, then a lift of W based at a vertex $u_i \in \hbox {fib}(u)$ is a walk ${\overline{W}}=(x_1,x_2,\dots ,x_n)$ beginning at $u_i$ such that the projection $\pi ({\overline{W}}):=(\pi (x_1),\pi (x_2),\ldots ,\pi (x_n))$ is equal to W. We denote by ${\mathcal {L}}(W)$ the set of all lifts of W based at $u_0$.

We say W is $\lambda$-reduced if $x_{i+1} \ne x_i^{-1}$ whenever $\lambda (x_i^{-1}) = 1$, and $x_n \ne x_1^{-1}$ whenever $\lambda (x_1) = 1$. Clearly, every reduced walk is $\lambda$-reduced.

Let $(\Delta ,\lambda ,\iota ,\zeta )$ be a ccv-graph and set $n = \hbox {lcm}\{\lambda (x)\iota (\mathop {\textrm{beg}}x) :x \in \textrm{D}(\Delta )\}$. Let $W=(x_1,x_2,\ldots ,x_k)$ be a walk in $\Delta$ and let $d = \gcd \{\iota (\mathop {\textrm{beg}}x_i):x_i \in W\}$. We define the endset of W as

$$\begin{aligned} \text {end}(W) = \sum \limits _{i=0}^k \zeta (x_i) + \langle d \rangle , \end{aligned}$$

where $\langle d \rangle$ denotes the subgroup of $\mathbb {Z}$ generated by d, and where the addition is computed modulo $\iota (\mathop {\textrm{end}}x_k)$.

Lemma 6.1

[26, Lemma 30] Let $(\Delta , \lambda ,\iota ,\zeta )$ be a ccv-graph and $\Gamma = \textrm{Cov}(\Delta , \lambda ,\iota ,\zeta )$. Let W be a uv-walk for some $u,v \in \textrm{V}(\Delta )$. If ${\overline{W}} \in {\mathcal {L}}(W)$, then the final vertex of ${\overline{W}}$ is $v_{j}$ for some $j \in \mathop {\textrm{end}}(W)$. Conversely, for every $j \in \mathop {\textrm{end}}(W)$ there exists a lift of W beginning at $u_0$ and ending at $v_j$.

Lemma 6.2

Let $(\Delta , \lambda ,\iota ,\zeta )$ be a ccv-graph and $\Gamma = \textrm{Cov}(\Delta , \lambda ,\iota ,\zeta )$. If C is a cycle in $\Gamma$, then $\pi (C)$ is a $\lambda$-reduced closed walk in $\Delta$ and $0 \in \mathop {\textrm{end}}(\pi (C))$.

Proof

Let C be a cycle in $\Gamma$. Clearly, C is a $u_au_a$-walk for some vertex $u_a \in \hbox {fib}(u)$ and some $u \in \textrm{V}(\Delta )$. Let x be a dart visited by $\pi (C)$ and suppose that $\pi (C)$ traces $x^{-1}$ immediately after x. We will show that $\lambda (x^{-1}) \ne 1$. Observe that since $\pi (C)$ traces x and $x^{-1}$ one after the other, there must exist a dart $x_i \in \hbox {fib}(x)$ and a dart $(x^{-1})_j \in \hbox {fib}(x^{-1})$ such that C traces $x_i$ and $(x^{-1})_j$ consecutively. Since C is a cycle, it is a reduced walk by definition, and thus $(x^{-1})_j \ne (x_i)^{-1}$. However, both $(x^{-1})_j$ and $(x_i)^{-1}$ belong to $\hbox {fib}(x^{-1})$. Moreover, since $x_i$ and $(x^{-1})_j$ are two consecutive darts of a walk, we have $\mathop {\textrm{beg}}(x^{-1})_j = \mathop {\textrm{end}}x_i = \mathop {\textrm{beg}}(x_i)^{-1}$. That is, there are two distinct darts in $\hbox {fib}(x^{-1})$ beginning at the same vertex. This implies that $\lambda (x^{-1}) \ge 2$.

Now suppose x and $x^{-1}$ are the first and the last darts traced by $\pi (C)$. Let $x_i \in \hbox {fib}(x)$ and $(x^{-1})_j \in \hbox {fib}(x^{-1})$ be the first and last darts traced by C, respectively. By an argument analogous to the one used in the previous case, we have that $(x^{-1})_j \ne x_i^{-1}$ but $\mathop {\textrm{beg}}(x^{-1})_j = \mathop {\textrm{beg}}x_i^{-1}$, and thus $\lambda (x)\ge 2$. This shows that $\pi (C)$ is $\lambda$-reduced.

To show that $0 \in \mathop {\textrm{end}}(\pi (C))$, recall that $\Gamma$ admits an automorphism $\rho$ that maps every dart $x_i$ to $x_{i+1}$. Then, $\rho ^{-a}$ maps the vertex $u_a$ to $u_0$, and thus $\rho ^{-a}(C)$ is a reduced closed walk beginning and ending at $u_0$. Moreover, $\rho ^{-a}(C) \in {\mathcal {L}}(\pi (C))$. Since the final vertex of $\rho ^{-a}(C)$ is $u_0$, it follows from Lemma 6.1 that $0 \in \mathop {\textrm{end}}(\pi (W))$. $\square$

Throughout the rest of the section, we will assume that $(\Delta ,\lambda )=\Delta _i$ for some $i \in \{1,\ldots ,11\}$, that $\Gamma$ is the cover of a ccv-extension $(\Delta ,\lambda ,\iota ,\zeta )$ of $\Delta _i$, and that $\pi :\Gamma \rightarrow \Delta$ is the covering projection. Note that $\Gamma$ is completely determined by the values of the voltages r and s, and $m:= \gcd \{\iota (u) :u \in \textrm{V}(\Delta )\}$. Indeed, $\Gamma$ is uniquely determined by the quadruple $(\Delta ,\lambda ,\iota ,\zeta )$. Recall that the index function $\iota$ is determined by its value on a single vertex along with the labelling $\lambda$, which is given. Let $u \in \textrm{V}(\Delta )$ be any vertex and for each $v \in \textrm{V}(\Delta ) {\setminus } \{u\}$ chose (arbitrarily) a uv-walk $W_v$. By equality (4.3), we have $\iota (v)=\lambda ^*(W_v)\iota (u)$ for all $v \in \textrm{V}(\Delta ) \setminus \{u\}$. Let c be the smallest positive integer such that $c \cdot \lambda ^*(W_v)$ is an integer for all $v \in \textrm{V}(\Delta ) {\setminus } \{u\}$. Then, $\iota (u)=c\cdot m$. Note that c depends only on $\lambda$ and our choice of u. Then, $\iota$ is completely determined by $\lambda$ and m. Finally, since we can assume $\zeta$ to be simplified, we know that every dart x underlying a semi-edge has voltage $\iota (\mathop {\textrm{beg}}x) / 2$, and any other dart not labelled r or s has voltage 0. The values of r and s, along with the function $\iota$, thus completely determine $\zeta$.

We are now ready to analyse the labelled graphs $\Delta _i$. The technique employed in the following pages relies mainly in finding a closed walk W of length n in $\Delta _i$ such that ${\mathcal {L}}(W)$ contains a cycle of length n, regardless of the specific values of the voltages r and s. Such a walk can often be found by finding an artefact $A_j$ in $\Delta _i$. If we suppose that $\Gamma$ is vertex-transitive, then for every vertex $v_i$ of $\Gamma$, at least one dart incident to $v_i$ must lie on an n-cycle. Then, by Corollary 6.2, this will imply that for every vertex $v \in \textrm{V}(\Delta )$ a specific dart incident to v lies on a closed walk $W'$ of length n such that $0 \in \mathop {\textrm{end}}(W')$. Since every element of $\mathop {\textrm{end}}(W')$ can be seen as a linear combination of m, r and s, $0 \in \mathop {\textrm{end}}(W')$ implies a relation between m, r and s, which along with the fact that $\gcd (m,r,s)=1$ (see item (5) of Lemma 3.8), is often enough to completely determine their values (up to a few options). This, in turn, determines the graph $\Gamma$.

Lemma 6.3

If $\Gamma$ is a vertex-transitive ccv-cover of $\Delta _{1}$, then $\Gamma$ is a bicirculant graph of order 12.

Proof

Let $(\Delta ,\lambda ,\iota ,\zeta )$ be a ccv-extension of $\Delta _1$ such that $\Gamma = \textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$. Let $\iota (c)=m$ and note that $\iota (d)=m$ as c and d are connected through a [1, 1]-edge. Similarly $\iota (a)=\iota (b)=2m$. Let $W=((ac)_0,(ca)_0,(ad)_0,(da)_0)$ and note that every reduced walk in ${\mathcal {L}}(W)$ is a cycle of length 4, as the darts traced by W induce the artefact $A_2$ (see Lemma 5.6). Then, every dart in the fibre of $(ac)_0$ or $(ad)_0$ lies on a 4-cycle. Since $\Gamma$ is vertex-transitive, every dart in the fibre of $(bb)_s$ (or of $(bb)_{-s}$) must lie on a 4-cycle. Suppose C is a 4-cycle (in $\Gamma$) through $b_0b_s$. Then, $\pi (C)$ is a $\lambda$-reduced walk of length 4 through $(bb)_s$. Clearly, $\pi (C) = ((bb)_s,(bb)_s,(bb)_s,(bb)_s)$ and $\mathop {\textrm{end}}(\pi (C)) = \{4s\}$. By Lemma 6.2, $0 \in \mathop {\textrm{end}}(\pi (C))$ and thus $4\,s \equiv 0$ ($\hbox {mod}\, 2\,m$). Since $0< s < m$, we have $2\,s = m$. This shows that $(b_0,b_s,b_{2s},a_{2s},c_{2s},a_{2s+m})$ is a 6-cycle in $\Gamma$ since $a_{2\,s+m} = a_0$ and $a_0 \sim b_0$. Then, the 6-signature of $\Gamma$ is $(\epsilon _1,\epsilon _2,\epsilon _3)$ where $\epsilon _i > 0$. That is, every dart of $\Gamma$ lies in at least one 6-cycle. In particular, there is a 6-cycle $C'$ through $c_0d_{-r}$. Then, $\pi (C')$ is a $\lambda$-reduced walk of length 6 through $(cd)_{-r}$. By inspecting Fig. 8, one can easily find all closed walks of length 6 whose first and second vertices are c and d, respectively, in the graph $\Delta _1$ of Fig. 8. The reader can easily and quickly verify that $\pi (C')$ must be one of

$$\begin{aligned} W_1&= ((cd)_{-r},(da)_0,(ac)_0,(cd)_{-r},(da)_0,(ac)_0),\\ W_2&= ((cd)_{-r},(da)_0,(ab)_0,(bb)_s,(ba)_0,(ac)_0),\\ W_3&= ((cd)_{-r},(da)_0,(ab)_0,(bb)_{-s},(ba)_0,(ac)_0). \end{aligned}$$

Now, $\mathop {\textrm{end}}(W_1)=\{-2r\}$, $\mathop {\textrm{end}}(W_2)=\{s-r\}$ and $\mathop {\textrm{end}}(W_3)=\{-s-r\}$. Since $0 \in \mathop {\textrm{end}}(W_i)$ for some $i \in \{1,2,3\}$, we see that one of the following holds modulo m,

$$\begin{aligned} -2r \equiv 0,\\ s-r \equiv 0,\\ -s-r \equiv 0. \end{aligned}$$

Since $0 \le r <m$ and $2\,s = m$, we see that either $r=0$ or $s=r$. However, $\gcd (m,r,s)=1$ by Lemma 3.8. Therefore, $r = s = 1$ and $m=2$. That is, the functions $\zeta$ and $\iota$ are completely determined and so is $\Gamma$. It can be verified that $\Gamma$ is a bicirculant isomorphic to the Franklin graph (see page 244 of [4] for definition and properties). $\square$

Lemma 6.4

If $\Gamma$ is a ccv-cover of $\Delta _{i}$, $i \in \{2,3,11\}$, then $\Gamma$ is not vertex-transitive.

Proof

Let $(\Delta ,\lambda ,\iota ,\zeta )$ be a ccv-extension of $\Delta _j$ and suppose $\Gamma := \textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ is vertex-transitive.

First, suppose $j = 2$. Let $\iota (d) = 2\,m$ and for $k \in \{0,1\}$ let $W_k=( (da)_0,(ab)_{kr},(bc)_0,(cb)_0,(ba)_{-kr},(ad)_{0})$. Observe that every edge incident to $a_0$ lies on a 6-cycle belonging to ${\mathcal {L}}(W_0) \cup {\mathcal {L}}(W_1)$. Then, $d_0d_m$ must lie on a 6-cycle C of $\Gamma$ and $\pi (C)$ is a $\lambda$-reduced closed walk of length 6. It is straightforward to see that no $\lambda$-reduced closed walk of length 6 in $\Delta _2$ traces the dart $(dd)_m$, a contradiction. Therefore, $\Gamma$ is not vertex-transitive.

Now, suppose $j = 3$. Let $\iota (d) = 2\,m$ and $W=( (da)_0,(ab)_r,(ba)_0,(ad)_0,(da)_0,(ab)_0,(ba)_{-r},(ad)_0)$. Observe that every edge incident to $a_0$ lies on an 8-cycle of ${\mathcal {L}}(W)$, which implies the existence of an 8-cycle C through $d_0d_m$, since $\Gamma$ is vertex-transitive. Then, $\pi (C)$ is a $\lambda$-reduced closed walk of length 8 through $(dd)_m$. Once more, one can verify that no such walk exists in $\Delta _3$. We conclude $\Gamma$ is not vertex-transitive.

Finally, suppose $j = 11$. Let $\iota (d) = m$ and note that since the voltage assignment is simplified, the darts incident to a or b have voltage m and those incident to c or d have voltage m/2. Since $\Gamma$ is connected, $\gcd (m/2,m)=1$, which implies that $m=2$. Note that the functions $\zeta$ and $\iota$ are thus completely determined, and so is the graph $\Gamma$. One can simply verify that $\Gamma$ is a non-vertex-transitive graph of order 12. $\square$

Lemma 6.5

If $\Gamma$ is a vertex-transitive ccv-cover of $\Delta _j$, with $j \in \{4,5\}$, then $\Gamma$ has less than 20 vertices.

Proof

Suppose $\Gamma =\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ is vertex-transitive where $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-extension of $\Delta _{4}$ and let $\iota (a)=m$. Since $\Delta _4$ has a [1, 3]-edge, $\Gamma$ must be arc-transitive by Lemma 5.5. Now, if $r \equiv 0$ ($\hbox {mod}\, m$), then $(d_0,a_0,c_m,a_m)$ is a 4-cycle of $\Gamma$ and by Corollary 5.3, $\Gamma$ has less than 20 vertices. Suppose that $r \not \equiv 0$ ($\hbox {mod}\, m$). For $i \in \{0,1\}$, let

$$\begin{aligned} W_i=((da)_0,(ab)_{ir},(bc)_0,(cb)_0,(ba)_{-ir},(ad)_0). \end{aligned}$$

Observe that every dart in the fibre of $(da)_0$ lies on 4 distinct 6-cycle in ${\mathcal {L}}(W_0) \cup {\mathcal {L}}(W_1)$ (see Fig. 9, left). Then, by Lemma 5.4$\Gamma$ has less than 20 vertices.

Fig. 9

For each of the two cases in the proof of Lemma 6.5, a subgraph of $\Gamma$ containing 4 distinct 6-cycles through the dart $d_0a_0$ (left) and through the dart $e_0c_0$ (right), respectively

Now, suppose $\Gamma :=\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ is vertex-transitive where $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-extension of $\Delta _{5}$ and consider the walk

$$\begin{aligned} W=((ec)_0,(ca)_0,(ad)_0,(da)_0,(ac)_0,(ce)_0). \end{aligned}$$

Observe that every dart in $e_0c_0$ lies on 4 distinct 6-cycle in ${\mathcal {L}}(W)$ (see Fig. 9, right) and by Lemma 5.4, $\Gamma$ has less than 20 vertices. $\square$

Lemma 6.6

If $\Gamma$ is a vertex-transitive ccv-cover of $\Delta _{6}$, then $\Gamma$ is a tricirculant of order 18.

Proof

Suppose $\Gamma :=\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ is vertex-transitive where $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-extension of $\Delta _{6}$. Then, for some $m \in \mathbb {Z}$ we have $\iota (c)=\iota (d)=m$ and $\iota (a)=\iota (b)=2\,m$. Let $W=((aa)_m,(ad)_0,(da)_0)$ and observe that every reduced walk in ${\mathcal {L}}(W)$ is a 3-cycle (see Lemma 5.6). Then, every dart in the fibre of $(aa)_m$ or $(ad)_0$ lies on a 3-cycle. Since $\Gamma$ is vertex-transitive, it must be 3-cycle-regular. In particular, every dart in the fibre of $(bb)_r$ lies on a 3-cycle and so, in $\Gamma$, there is a 3-cycle C through the edge $b_0b_r$. Then, $\pi (C)$ is a $\lambda$-reduced closed walk of length 3 that traces $(bb)_r$. It is straightforward to see that necessarily $\pi (C)=((bb)_r,(bb)_r,(bb)_r)$. Moreover, by Lemma 6.2, $0 \in \mathop {\textrm{end}}(\pi (C))=\{3r\}$ and so

$$\begin{aligned} 3r \equiv 0 \quad (\hbox {mod}\, 2m). \end{aligned}$$

(6.1)

Now, every dart in the fibre of $(cc)_s$ must also lie on a 3-cycle, and by an analogous argument,

$$\begin{aligned} 3s \equiv 0 \quad (\hbox {mod}\, m). \end{aligned}$$

(6.2)

Since $\Gamma$ is connected, by Lemma 3.8 we see that $\gcd (m,r,s) = 1$ and by (6.1) and (6.2), we see that the only possibility is that $m=3$, $r=2$ and $s=1$. One can readily verify that $\Gamma$ is isomorphic to the truncation of $K_{3,3}$, and thus is a vertex-transitive tricirculant of order 18. $\square$

Lemma 6.7

If $\Gamma$ is a vertex-transitive ccv-cover of $\Delta _{7}$, then $\Gamma$ is a bicirculant of order 12.

Proof

Suppose $\Gamma =\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ is vertex-transitive where $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-extension of $\Delta _{7}$. Then, $\iota (c)=\iota (a)=2\,m$ and $\iota (b) = \iota (d) = m$ for some $m \in \mathbb {Z}$. Let $W=((ad)_0,(da)_0,(ab)_0,(ba)_0)$ and observe that every reduced walk in ${\mathcal {L}}(W)$ is a 4-cycle. In particular, $a_0b_0$ and $a_0d_0$ lie on a 4-cycle, and thus, the vertex-transitivity of $\Gamma$ implies that there is a 4-cycle C through $c_0c_r$. It follows that $\pi (C)$ is a $\lambda$-reduced closed walk of length 4 through the dart $(cc)_r$. It is plain to see that $\pi (C)=((cc)_r,(cc)_r,(cc)_r,(cc)_r)$ and thus $\mathop {\textrm{end}}(\pi (C))=\{4r\}$. Then, $4r \equiv 0$ ($\hbox {mod}\, 2\,m)$ and $\gcd (m,r)=1$. Since $0< r < m$, we see that $r = 1$ and $m=2$. Then, $\Gamma$ is a cubic bicirculant of order 12 and is in fact isomorphic to the Franklin graph. $\square$

Lemma 6.8

If $\Gamma$ is a vertex-transitive ccv-cover of $\Delta _{8}$, then $\Gamma$ is the triangular prism $\textrm{GP}(3,1)$.

Proof

Let $\Gamma =\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ be vertex-transitive where $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-extension of $\Delta _{8}$. Let $\iota (c)=m$ so that $\iota (a)=\iota (b)=2m$. Consider the walk $W=( (aa)_m,(ab)_0,(bb)_m,(ba)_0)$ and see that both $a_0a_m$ and $a_0b_0$ lie on a 4-cycle in ${\mathcal {L}}(W)$. Since $\Gamma$ is vertex-transitive, then one of $d_0a_0$ or $d_0a_m$ must lie on a 4-cycle C. Then, $\pi (C)$ is a $\lambda$-reduced closed walk of length 4 through the dart $(da)_{0}$. Clearly $\pi (C) = ((da)_0,(ab)_0,(bc)_0,(cd)_{-r})$ and $\mathop {\textrm{end}}(\pi (C))=\{-r\}$. Then, by Lemma 6.2 we have $r \equiv 0$ ($\hbox {mod}\, m$). Since $\gcd (m,r)=1$ and $r < m$, we see that $m = 1$ and $r=0$. Then, $\Gamma$ can be seen to be isomorphic to the triangular prism. $\square$

Lemma 6.9

If $\Gamma$ is a ccv-cover of $\Delta _{9}$, then $\Gamma$ is not vertex-transitive.

Proof

Let $\Gamma =\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ where $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-extension of $\Delta _{9}$. Observe that $\iota (a) = 2\cdot \iota (b) = 3\cdot \iota (d)$. Moreover, $\iota (b)$ is even as b is incident to a semi-edge. Then, $\iota (a)$ is divisible by 12. That is, for some $m \in \mathbb {Z}$ we have $\iota (a)=\iota (c)=12\,m$, $\iota (b) = 6\,m$, $\iota (d)=4\,m$ and the order of $\Gamma$ is 34m. Suppose $\Gamma$ is vertex-transitive and consider the walk

$$\begin{aligned} W=( (da)_0,(ab)_0,(ba)_0,(ad)_0,(da)_0,(ab)_0,(ba)_0,(ad)_0). \end{aligned}$$

Observe that every dart beginning at $d_0$ lies on an 8-cycle belonging to ${\mathcal {L}}(W)$. This implies the existence of a $\lambda$-reduced walk $W'$ of length 8 through the dart $(bb)_{3m}$. Observe that then $W'$ must be one (or the inverse) of the following 6 walks, where $i \in \{-1,1\}$:

$$\begin{aligned} W_{1,i}= & {} ((bb)_{3m}, (ba)_0, (ac)_0, (cc)_{ir}, (cc)_{ir}, (cc)_{ir}, (ca)_0, (ab)_0), \\ W_{2,i}= & {} ((bb)_{3m}, (ba)_0, (ac)_0, (cc)_{ir}, (ca)_{0}, (ad)_{0}, (da)_0, (ab)_0), \\ W_{3,i}= & {} ((bb)_{3m}, (ba)_0, (ad)_0, (da)_{0}, (ac)_{0}, (cc)_{ir}, (ca)_0, (ab)_0). \end{aligned}$$

Let ${\mathcal {W}}$ be the set containing the six walks $W_{j,i}$, $j \in \{1,2,3\}$ and $i \in \{-1,1\}$, along with their inverses. Denote by $\mathop {\textrm{end}}({\mathcal {W}})$ the union of endsets over the elements of ${\mathcal {W}}$. A tedious but straightforward computation shows that

$$\begin{aligned} \mathop {\textrm{end}}({\mathcal {W}})=\{\pm 2m, \pm (m+r),\pm (m-r),\pm (3m+r),\pm (3m+3r)\}. \end{aligned}$$

Then, $z \equiv 0$ ($\hbox {mod}\, 6\,m$) for some $z \in \mathop {\textrm{end}}({\mathcal {W}})$. This implies that $m=1$ and $r = km$ for some $k \in \{1,3,5\}$. Then, $\Gamma$ is one of three possible graphs of order 34 (observe that $\Gamma$ is completely defined by the values of r and m). One can check that in neither one of the three possible cases is $\Gamma$ vertex-transitive. $\square$

Fig. 10

The 8 distinct 8-cycles through the dart $d_0a_0$ in the proof of Lemma 6.10

Lemma 6.10

If $\Gamma$ is a ccv-cover of $\Delta _{10}$, then $\Gamma$ is not vertex-transitive.

Proof

Let $\Gamma =\textrm{Cov}(\Delta ,\lambda ,\iota ,\zeta )$ where $(\Delta ,\lambda ,\iota ,\zeta )$ is a ccv-extension of $\Delta _{10}$. Suppose $\Gamma$ is vertex-transitive. Since $\Delta _{10}$ has a [1, 3]-edge, $\Gamma$ is arc-transitive. For some $m \in \mathbb {Z}$ we have $\iota (e)=m$, $\iota (c)=3\,m$, $\iota (a)=\iota (b)=6\,m$ and $\iota (d)=2\,m$. Observe that the order of $\Gamma$ is 18m. As one can verify with the census of cubic vertex-transitive graphs [23], no ccv-cover of $\Delta _{10}$ is vertex-transitive if $m \in \{1,2\}$. Thus assume that $m > 2$. Furthermore, $r \not \equiv 0$ ($\hbox {mod}\, m$), for otherwise $m=1$ (since $\gcd (m,r)=1$). Now, for $i,j \in \{0,1\}$ and $k \in \{2,4\}$ consider the walks in $\Gamma$:

$$\begin{aligned} W_{i,j}= & {} (d_0,a_{0},b_{ir},c_{ir},e_{ir},c_{(1+j)m + ir},b_{(4-2j)m + ir},a_{(4-2j)m},d_0),\\ W'_{i,k}= & {} (d_0,a_0,b_{(1-i)r},a_{(1-2i)r},d_{(1-2i)r},a_{km+(1-2i)r},b_{km+(1-i)r},a_{km}). \end{aligned}$$

Note that each of these 8 walks is an 8-cycle through $a_0d_0$ (see Fig. 10). Since $\Gamma$ is arc-transitive, there must be 8 distinct 8-cycles through $c_0b_0$. Now, consider the walks

$$\begin{aligned} W_1= & {} ((cb)_0, (ba)_{0}, (ad)_0, (da)_0, (ab)_0, (bc)_0, (cd)_0, (dc)_0), \\ W_2= & {} ((cb)_0, (ba)_{-r}, (ad)_0, (da)_0, (ab)_{r}, (bc)_0, (cd)_0, (dc)_0), \\ W_3= & {} ((cd)_0, (ba)_{0}, (ab)_{r}, (bc)_0, (cb)_0, (ba)_{-r}, (ab)_{0}, (bc)_0), \\ W_4= & {} ((cd)_0, (ba)_{-r}, (ab)_{0}, (bc)_0, (cb)_0, (ba)_{0}, (ab)_{r}, (bc)_0) \end{aligned}$$

(see Fig. 11). Observe that for all $i \in \{1,2,3,4\}$, all lifts of $W_i$ that trace the dart $c_0b_0$ are 8-cycles. There are exactly 6 such cycles. It follows that there are an additional two 8-cycles through $c_0b_0$ that do not project to any of the four walks $W_i$, $i \in \{1,2,3,4\}$. Each of these two cycles projects to a $\lambda$-reduced closed walk of length 8 based at c and visiting the dart $(cb)_0$. Moreover, such projections must be different than $W_i$ with $i \in \{1,2,3,4\}$. Let ${\mathcal {W}}$ be the set of all $\lambda$-reduced closed walks of length 8 based at c and visiting the dart $(cb)_0$, that are distinct from $W_i$ with $i \in \{1,2,3,4\}$. Let $\mathop {\textrm{end}}({\mathcal {W}})$ be the union of the endsets of all the elements of ${\mathcal {W}}$. A computer assisted calculation shows that $\mathop {\textrm{end}}({\mathcal {W}}) = \{\pm (2\,m + r), \pm (m+2r),\pm (m+r),\pm (r),\pm (2r),\pm (3r),\pm (2\,m+2r)\}$. Then, $z \equiv 0$ ($\hbox {mod}\, 3\,m$) for some $z \in \mathop {\textrm{end}}{\mathcal {W}}$. This implies that $m=1$ and $r \in \{1,2,3,4,5\}$ or $m = 2$ and $r \in \{5,7\}$, a contradiction. We conclude that $\Gamma$ is not vertex-transitive. $\square$

Fig. 11

Two subgraphs of $\Gamma$ in the proof of Lemma 6.10. On the left, a subgraph containing all lifts of $W_1$ that visit $c_0$ (8-cycles through $c_0b_0$ shown in bold edges). On the right, a subgraph containing all lifts of $W_3$ and $W_4$ that visit $c_0$

Up to this point we have shown that none of the labelled graphs $\Delta _i$ with $i \in \{1,\ldots ,11\}$ admit a vertex-transitive ccv-covers with more than 20 vertices. Since the graphs in Fig. 7 all admit vertex-transitive ccv-covers with more than 20 vertices, it follows that the set ${{\mathcal {Q}}}$ consists of these eight graphs and possibly the graph $\Delta _{12}$ (it will be shown in Sect. 6.1 that $\Delta _{12}$ does in fact admit infinitely many vertex-transitive ccv-covers and thus belongs to ${{\mathcal {Q}}}$). Since the graphs in Fig. 7 have at most 3 vertices and all of their edges are of type [1, 1], we see that their generalised cyclic covers are k-multicirculants for some $k\le 3$. The following proposition summarises the contents of this section.

Proposition 6.11

Let $\Gamma$ be a cubic vertex-transitive graph of order $n>20$ admitting an automorphism of order n/3 or greater. Then, either $\kappa (\Gamma ) \in \{1,2,3\}$ or $\Gamma$ is a ccv-cover of $\Delta _{12}$.

6.1 The Graph $\Delta _{12}$

Fig. 12

The voltage assignment giving rise to the graph $\Gamma _{12}(m,r,s)$

Let m be a positive integer, and let r and s be two distinct elements of $\mathbb {Z}$. Let $\Delta _{12}(m,r,s)$ be the ccv-extension of $\Delta _{12}$ shown in Fig. 12, where voltages are shown in bold characters next to each edge and $\iota (a) =m$. It follows from equality (3.1) that $\iota (u) = \iota (v) = 2\,m$ and $\iota (a) = \iota (b) = m$. As the final step in the proof of Theorem 1.1, we need to prove the following:

Theorem 6.12

Let m, r, s, $m> 3$, be positive integers. If the cyclic generalised cover $\Gamma =\Gamma _{12}(m,r,s)$ arising from $\Delta _{12}(m,r,s)$ is connected and vertex-transitive, then m is odd and $\Gamma \cong \textrm{SDW}(m,3)$. Conversely, if m is odd, then $\textrm{SDW}(m,3)$ is isomorphic to $\Gamma _{12}(m,1,2)$, is connected and vertex-transitive and admits an automorphism of order 2m.

Proof

Recall that $\Gamma _{12}(m,r,s)$ admits an automorphism $\rho$ of order 2m whose orbits on vertices and darts are precisely the fibres of vertices and darts. Moreover, the automorphism $\rho ^m$ fixes the 2m vertices in the fibres $\hbox {fib}(a)$ and $\hbox {fib}(b)$; in particular, $\Gamma _{12}(m,r,s)$ admits a non-trivial automorphism that fixes one third of the vertices of the graph.

Suppose first that the girth of $\Gamma$ is less then 6. Then, by Lemma 5.1 (see also [28, Theorem 1.5]) and the fact that $\Gamma$ has at least 24 vertices, it follows that $\Gamma$ is isomorphic to the Möbius ladder $\textrm{Moeb}(6m)$ or to the prism $\textrm{Prism}(3m)$. However, every non-trivial automorphism of these graphs fixes at most 4 vertices, yielding a contradiction. Hence, the girth of $\Gamma$ is at least 6. Now observe that $\Gamma$ contains two 6-cycles $C_1:=(u_0,a_0,u_m,v_m,b_m,v_0)$ and $C_2:=(u_0,a_0,u_m,v_{m+r},b_{m+r},v_r)$, implying that its girth is 6.

Let $(\alpha , \beta , \gamma )$, $\alpha \le \beta \le \gamma$, be the 6-signature of $\Gamma$. Note that the edge $\{u_0,a_0\}$ lies on both of the cycles $C_1$ and $C_2$, while each of the remaining two edges incident with $u_0$ lies on precisely one of them. This shows that $\alpha , \beta \ge 1$ and $\gamma \ge 2$. Similarly, since both $C_1$ and $C_2$ pass through the edges $\{a_0,u_0\}$ and $a_0,u_m\}$, incident with $a_0$, we see that $\beta , \gamma \ge 2$. Moreover, since $\alpha \ge 1$, there must a third 6-cycle $C_3$ passing through the edge $\{a_0, b_s\}$. Since $C_3$ also passes through one of the edges $\{a_0,u_0\}$, $\{a_0,u_m\}$, it follows that $\gamma \ge 3$. Finally, since $\Gamma$ admits the automorphism $\rho ^m$ (where $\rho$ is the canonical covering transformation) of order 2 fixing a vertex and swapping two of its neighbours, we see that two of the parameters $\alpha , \beta , \gamma$ must be equal. By Lemma 5.1 (see also [29, Theorem 1]), it follows that $\Gamma \cong \textrm{SDW}(m,3)$. Finally, as mentioned in Remark 5.2 (and proved in [29, Proposition 5]), the automorphism group of $\textrm{SDW}(m,3)$, $m\not = 3$, equals $S_3 \times D_m$ and thus contains an element of order 2m if and only if m is odd.

To conclude the proof of the theorem, assume that m is odd, $m>3$, and consider the mapping $\varphi :\textrm{V}(\Gamma _{12}(m,1,2)) \rightarrow \textrm{V}(\textrm{SDW}(m,3))$ given by

$$\begin{aligned} \varphi (i,0,0)= & {} b_{i+1}; \\ \varphi (i,0,1)= & {} a_i; \\ \varphi (i,1,0)= & {} \left\{ \begin{array}{ll} u_{i+m} &{} \hbox { if } i \hbox { is even}; \\ u_{i} &{} \hbox { if } i \hbox { is odd}; \end{array}\right. \\ \varphi (i,1,1)= & {} \left\{ \begin{array}{ll} v_{i+1} &{} \hbox { if } i \hbox { is even}; \\ v_{i+m+1} &{} \hbox { if } i \hbox { is odd}; \end{array}\right. \\ \varphi (i,2,0)= & {} \left\{ \begin{array}{ll} u_{i} &{} \hbox { if } i \hbox { is even;} \\ u_{i+m} &{} \hbox { if } i \hbox { is odd;} \end{array}\right. \\ \varphi (i,2,1)= & {} \left\{ \begin{array}{ll} v_{i+m+1} &{} \hbox { if } i \hbox { is even;} \\ v_{i+1} &{} \hbox { if } i \hbox { is odd;} \end{array}\right. \end{aligned}$$

for all $i \in \{0,1, \ldots , m-1\}$, where the indices at $b_j$’s and $a_j$’s are computed modulo m, while those at $u_j$’s and $v_j$’s are computed modulo 2m. The isomorphism $\varphi$ is depicted in Fig. 13 where each vertex of $\textrm{SDW}(m,3)$ is labelled with its $\varphi$-image.

Fig. 13

A section of $\Gamma _{12}(m,1,2)$ with $m \ge 3$

It is obvious that $\varphi$ is a graph isomorphism. $\square$

By [29, Proposition 5] (see also Remark 5.2), the automorphism group of $\textrm{SDW}(m,3)$ is isomorphic to $S_3\times D_m$, unless $m=3$, in which case $\textrm{SDW}(m,3)$ is the unique cubic arc-transitive graph on 18 vertices, also called the Pappus graph. From this, it is easy to deduce the parameter $\kappa$ and ${\eta }$ for the split wreath graph $\textrm{SDW}(m,3)$:

Lemma 6.13

Let $\Gamma = \textrm{SDW}(m,3)$ for some integer $m\ge 3$. Then, one of the following holds:

• m is not divisible by 3 and $\eta \mathrm (\Gamma ) = \kappa (\Gamma ) = 2$;

• $m \equiv 0$ $(\hbox {mod}\, 6)$, and ${\eta }(\Gamma ) = \kappa (\Gamma ) = 6$;

• $m \equiv 3$ $(\hbox {mod}\, 6)$, $m\not = 3$, and ${\eta }(\textrm{SDW}(m,3)) = 3$ while $\kappa (\textrm{SDW}(m,3))= 6$;

• $m=3$, $\Gamma$ is isomorphic to the Pappus graph and $\kappa (\Gamma ) = 3$ while $\eta \mathrm (\Gamma ) = 3/2$.

7 Proof of Theorem 1.1

Using the results proved in the previous sections, it is now not difficult to prove Theorem 1.1. Before we proceed to the proof, we will need the lemma below, characterising those cyclic Haar graphs that are circulant graphs.

Lemma 7.1

For an integer $m \ge 5$, a connected cyclic Haar graph $\textrm{H}(m,x,y)$ is a circulant if and only if m is odd and $\{x,y\} = \{a,2a\}$ or $\{x,y\} = \{a,-a\}$ for some $a \in \mathbb {Z}$ such that $\gcd (m,a)=1$.

Proof

Suppose that $\Lambda =\textrm{H}(m,x,y)$, $\gcd (m,x,y) = 1$, is a circulant. For $i\in \mathbb {Z}_m$, we let $u_i$ and $v_i$ denote the vertices (i, 0) and (i, 1), respectively, and recall that the neighbours of $u_i$ in $\Lambda$ are $v_i, v_{i+x}$ and $v_{i+y}$.

Since $\Lambda$ is a circulant, it is isomorphic to a prism or to a Möbius ladder. In both cases, the girth of $\Gamma$ is 4 and at every vertex there is an edge belonging to two 4-cycles, none of these 4-cycles sharing a 2-path (recall that we are assuming that $m \ge 5$ and thus the order of $\Lambda$ is at least 10). Observe also that exactly one of the graphs $\Lambda$, $\textrm{H}(m,-x, y-x)$ and $\textrm{H}(m, x-y, -y)$, isomorphic to $\Lambda$, is such that the edge incident with the vertex (0, 0) belonging to two 4-cycles is $e_0=\{u_0, v_0\}$. Denote this graph $\textrm{H}(m,a,b)$ (that is, (a, b) is one of $(x,y), (-x,y-x)$ or $(x-y,-y)$, or equivalently, (x, y) is one of (a, b), $(-a,b-a)$ or $(a-b,-b)$).

One of the two 4-cycles passing through $e_0$ passes also through the edge $e_1=\{u_0,v_a\}$, while the other passes through $e_2=\{u_0,v_b\}$. Since the neighbours of $v_0$ are $u_0, u_{-a}$ and $u_{-b}$, for these two edges to form a 4-cycle together with the edge $e_0$, either $u_{-a}$ is adjacent to $v_a$ and $u_{-b}$ to $v_{b}$, or $u_{-b}$ is adjacent to $v_a$ and $u_{-a}$ to $v_{b}$. In the first case, both 2a and 2b belong to the set $\{0,a,b\}$, while in the second case, $a+b \in \{0,a,b\}$, which forces $a+b = 0$ (since $a\not = 0 \not = b$).

Let us consider the first case. Observe that $2a \not = a$ and $2b \not = b$. If $2a=0$, then m is even, $a=m/2$ and $2b=a$. Since $\gcd (m,a,b) = 1$, this forces $m=4$, contradicting our assumption that $\Lambda$ has at least 10 vertices. A similar contradiction is obtained if $2b=0$. This leaves us with the possibility that $2a=b$ and $2b =a$. But then $a + b =0$, and we find ourselves in the second case.

Therefore, the second case occurs, that is, $a+b = 0$. Since $\gcd (m,a,b) = 1$, this implies that $\gcd (m,a) = 1$ and $b=-a$. But then (x, y) is one of the pairs $(a,-a)$, $(-a,-2a)$ or (2a, a).

To summarise, if a connected cubic cyclic Haar graph $\textrm{H}(m,x,y)$ with $m\ge 5$ is a circulant, then $\{x,y\} = \{a, 2a\}$ or $\{x,y\} = \{a, - a\}$ for some $a \in \mathbb {Z}_m$ with $\gcd (m,a)=1$. Furthermore, the graphs $\textrm{H}(m,a,2a)$ and $\textrm{H}(m,a,-a)$ are isomorphic to the prism $\textrm{Prism}(m)$ whenever m is even, and thus cannot be circulants. It follows that m must be odd, as required.

For the converse, let $m,a \in \mathbb {Z}$ be such that $m \ge 5$, m is odd and $\gcd (m,a)=1$. If $\Lambda = \textrm{H}(m,a,-a)$, then the mapping given by $u_i \mapsto v_{i+r}$ and $v_i \mapsto u_{i+r}$ is a circulant automorphism of $\Lambda$. On the other hand if $\Lambda = \textrm{H}(m,a,2a)$ then the mapping given by $u_i \mapsto v_i$ and $v_i \mapsto u_{i-2r}$ is a circulant automorphism of $\Lambda$. $\square$

We are now ready to prove Theorem 1.1. As mentioned in Sect. 2.3, the validity of the theorem for graphs on at most 20 vertices can easily be checked by consulting the census of cubic vertex-transitive graphs [23].

Now, as in the statement of Theorem 1.1, let $\Gamma$ be a cubic vertex-transitive graph of order n, $n>20$, admitting an automorphism of order at least $\frac{n}{3}$. We need to show that then one of the claims (1) – (4) of Theorem 1.1 holds.

Observe first that by combining Proposition 6.11 with Theorem 6.12, $\kappa (\Gamma ) \in \{1,2,3\}$ or $\Gamma$ is isomorphic to $\textrm{SDW}(m,3)$ with m odd (and $m\not = 3$ since we are assuming that $\Gamma$ has more than 20 vertices). In the latter case, by Lemma 6.13, we see that $\kappa (\Gamma ) \le 3$ or $m \equiv 3\> (\hbox {mod}\, 6)$ (in which case $\kappa (\Gamma ) = 6$).

To summarise, either $\kappa (\Gamma ) \in \{1,2,3\}$ or claim (4) of Theorem 1.1 holds.

Suppose now that $\kappa (\Gamma ) \in \{1,2,3\}$. If $\Gamma$ is a circulant, then, by definition, $\Gamma \equiv \textrm{Cay}(\mathbb {Z}_{2m};S)$, where $S=\{r,-r,m\}$ for some $r\in \mathbb {Z}_{2\,m}$, $r\not = 0$. By connectivity of $\Gamma$, we may assume that $\gcd (r,m) = 1$, implying that there exists $s\in \mathbb {Z}_{2\,m}$, $\gcd (s,2\,m) =1$, such that $rs = 1$, or r is even, m is odd and $rs=2$ in $\mathbb {Z}_{2m}$. Note that $\Gamma$ is then isomorphic to $\textrm{Cay}(\mathbb {Z}_{2\,m};\{1,-1,m\}) \cong \textrm{Moeb}(2\,m)$ (in the first case) or to $\textrm{Cay}(\mathbb {Z}_{2\,m};\{2,-2,m\}) \cong \textrm{Prism}(m)$ (in the second case). In particular, claim (1) of Theorem 1.1 holds in this case.

If $\Gamma$ is a bicirculant, then it can be deduced from [22, Propositions 3 and 4] and [3, Theorem 7 and Corollay 8] (see also [25, Theorem 1.1 and Remark 1.2]) that $\Gamma$ is isomorphic either to a prism $\textrm{Prism}(m)$, or to a Möbius ladder $\textrm{Moeb}(n)$, or to one of the vertex-transitive generalised Petersen graphs $\textrm{GP}(m,r)$ with $2\le r < m/2$, $r^2\equiv \pm 1\> (\hbox {mod}\, m)$, or to a cyclic Haar graph $\textrm{H}(m,r,s)$ with $\gcd (m,r,s) = 1$.

If $\Gamma$ is a prism or a Möbius ladder, then it is not a circulant only if it is isomorphic to a prism $\textrm{Prism}(m)$ with m even (and then claim (2a) of Theorem 1.1 holds). Further, since the girth of a generalised Petersen graph $\textrm{GP}(m,r)$ is at least 5 unless $m\le 4$ or $r=1$, we see that a generalised Petersen graph $\textrm{GP}(m,r)$ is a circulant if and only if $r=1$ and m is odd (in which case it is a prism). In particular, if $\Gamma$ is a generalised Petersen graph which is not a circulant, then claim (2b) of Theorem 1.1 holds.

If $\Gamma$ is a connected cyclic Haar graph, that is $\Gamma =\textrm{H}(m,r,s)$ with $m> 10$ and $\gcd (m,r,s) = 1$, then by applying the permutation $\varphi _{\alpha ,0}$ for an appropriate $\alpha$, we may assume that r divides m (where r is represented as a positive integer smaller than m), and thus that $\gcd (r,s) = 1$. Under this assumption, by Lemma 7.1$\Gamma$ is then a circulant if and only if m is odd and $\{r,s\} = \{1, 2\}$ or $\{r,s\}=(1,m-1)$. We have thus shown that the claim (2c) of Theorem 1.1 holds in this case.

If $\Gamma$ is a tricirculant but not a bicirculant, then by [24, Theorems 1.1, 4.3 and 5.3], $\Gamma$ is either the Tutte’s 8-cage (on 30 vertices), the truncated tetrahedron (on 12 vertices) or isomorphic to one of the graphs $\textrm{X}(m)$ or $\textrm{Y}(m)$ with $m \equiv 3\> (\hbox {mod}\, 6)$. Note that claims (3) of Theorem 1.1 holds in this case.

For the converse, it is clear that the circulants, bicirculants and tricirculant appearing in parts (1), (2) and (3) of Theorem 1.1 all admit an automorphism of order at least one third of the order of the graph. The graph $\textrm{SDW}(m,3)$ with $m \equiv 3\> (\hbox {mod}\, 6)$ has order 6m and admits, by construction, an automorphism with two orbits of size 2m, namely, the canonical covering transformation $\rho$. This completes the proof of Theorem 1.1.

8 Relationship Between $\kappa (\Gamma )$ and $\eta (\Gamma )$ and Open Problems

Let us conclude the paper with a discussion on the interplay between the parameters $\kappa (\Gamma )$ and $\eta \mathrm (\Gamma )$. First, note that none of the functions ${\eta }(\Gamma )$ and $\kappa (\Gamma )$ can be bounded above by a constant, even when restricted to the class of cubic vertex-transitive graphs. Namely, if there were a constant C such that ${\eta }(\Gamma ) \le C$ holds for all graphs $\Gamma$, then $\max \{o(g): g \in \textrm{Aut}(\Gamma )\} \ge |\textrm{V}(\Gamma )|/C$, or in other words, the parameter $\textrm{meo}(\Gamma ):=\max \{o(g): g \in \textrm{Aut}(\Gamma )\}$ is bounded below by a linear function of $|\textrm{V}(\Gamma )|$. However, it was shown in [27] that there exists an infinite family $\{{\Gamma }_{i}\}_{i\in \mathbb {N}}$ of cubic vertex-transitive graphs with $\textrm{meo}(\Gamma _i)$ growing slower than any logarithmic function of $|\textrm{V}(\Gamma _i)|$. This implies that there is no constant C such that ${\eta }(\Gamma ) \le C$ for all cubic vertex-transitive graph $\Gamma$. Since $\eta \mathrm (\Gamma ) \le \kappa (\Gamma )$ holds for all $\Gamma$, this implies that there is no upper bound on $\kappa (\Gamma )$.

Let us mention at this point that a somewhat similar problem was raised in [5], where it was conjectured that the value

$$\begin{aligned} m(n):=\min \{ \frac{|\textrm{V}(\Gamma )|}{\kappa (\Gamma )}: \Gamma \hbox { a cubic vertex-transitive graph on at most } n \hbox { vertices} \} \end{aligned}$$

tends to $\infty$ as n grows to $\infty$, or in other words, for every integer n, there is a constant $c_n$ such that every cubic vertex-transitive graph on more than n vertices admits a semiregular element of order at least $c_n$. However, in [30], an infinite family of cubic vertex-transitive graphs was constructed in which every semiregular automorphism has order at most 6, proving this conjecture wrong in general (but proved to be correct when restricted to arc-transitive or Cayley graphs [20]). On the other hand, it was proved recently in [2] that $m(n) \ge 6$ for n sufficiently large.

While $\kappa (\Gamma )$ can take an arbitrary large value, a question arises whether the parameter $\kappa (\Gamma )$ can be bounded above in terms of $\eta (\Gamma )$ where $\Gamma$ ranges through the class of cubic vertex-transitive graphs. More precisely, we are interested in the following:

Question 8.1

For which positive integers r does there exist an integer $k_r$ such that $\kappa (\Gamma ) \le k_r$ for all but finitely many cubic vertex-transitive graphs satisfying ${\eta }(\Gamma ) \le r$?

If for some r an integer $k_r$ as above exists, then let f(r) be the smallest such integer $k_r$. A direct consequence of Theorem 1.1 is that f(r) can be defined at least for $r\in \{1,2,3\}$ and that $f(1) = 1$, $f(2) =2$ and $f(3)=6$. Let us conclude this paper by posing the following:

Question 8.2

If the function f(r) is defined for all r, what is its asymptotic behaviour as $r\rightarrow \infty$? Is f(r) unbounded? If so, can it be bounded by a linear and/or polynomial function of r?