Half-Arc-Transitive Graphs and the Fano Plane

Abstract

A subgroup G of the automorphism group of a graph $\Gamma$ acts half-arc-transitively on $\Gamma$ if the natural actions of G on the vertex-set and edge-set of $\Gamma$ are both transitive, but the natural action of G on the arc-set of $\Gamma$ is not transitive. When $G ={\text{Aut}}(\Gamma )$ the graph $\Gamma$ is said to be half-arc-transitive. Given a bipartite cubic graph with a certain degree of symmetry two covering constructions that provide infinitely many tetravalent graphs admitting half-arc-transitive groups of automorphisms are introduced. Symmetry properties of constructed graphs are investigated. In the second part of the paper the two constructions are applied to the Heawood graph, the well-known incidence graph of the Fano plane. It is proved that the members of the infinite family resulting from one of the two constructions are all half-arc-transitive, and that the infinite family resulting from the second construction contains a mysterious family of arc-transitive graphs that emerged within the classification of tightly attached half-arc-transitive graphs of valence 4 back in 1998 and 2008.

1 Introduction

The theory of half-arc-transitive graphs and graphs admitting half-arc-transitive group actions (see Sect. 2 for definitions of these and most of the other terms appearing in Introduction) started its development half a century ago when Tutte [25] showed that all such graphs are necessarily of even valence. Although some papers in the literature deal with half-arc-transitive graphs of all possible valences (see for instance [20] and the references therein) most of the work has focused on graphs of the smallest interesting valence, namely 4 (see for instance [1, 18, 21] and the references therein). The results from [1, 21] indicate that (cyclic) covers of tetravalent half-arc-transitive graphs and graphs admitting such group actions need to be thoroughly investigated if we are to make a significant step forward in understanding the class of tetravalent half-arc-transitive graphs as a whole. One of the goals of the present paper is to introduce and study two particular covering constructions arising from cubic bipartite graphs with an appropriate degree of symmetry. The constructed covers all admit a half-arc-transitive group of automorphisms.

We believe the two constructions are interesting on their own but there is another motivation for their study. In the long term program of trying to classify or at least characterize all tetravalent half-arc-transitive graphs important steps forward were obtained by investigating the local structure of such graphs via the so-called alternating cycles and attachment sets. The foundations of this method, which are based on a rather simple observation that a half-arc-transitive action of a group G on a graph $\Gamma$ gives rise to two paired G-induced orientations of edges of $\Gamma$, were laid out by Marušič in 1998 [13]. The nicest possibility in this context occurs when two non-disjoint alternating cycles meet in half of their vertices—such graphs are called tightly-attached. The tightly-attached tetravalent half-arc-transitive graphs were classified in papers [13] and [22] from 1998 and 2008, respectively. In the process of obtaining this classification a very mysterious family of arc-transitive graphs emerged. Except for the smallest example (of order 21) the mysterious graphs are all of order divisible by $42 = 6\cdot 7$ but not by $7^2$ and for each positive integer of the form 42m, where $7 \not \mid m$, precisely one member of order 42m from this family exists. We call these graphs mysterious due to the fact that at that time there did not seem to be a very natural explanation for their arc-transitivity. The authors of [13, 22] simply found one explicit “unexpected” automorphism (which does not respect the “tightly attached structure”) that ensured arc-transitivity of the graphs in question. They did not pursue the question of the “true” origin of these extra symmetries nor the question of how many of these extra symmetries the graphs admit. For the purposes of the above mentioned classification arc-transitivity of these graphs sufficed for their elimination from the list of all tightly attached half-arc-transitive graphs.

It turns out that tightly attached tetravalent half-arc-transitive graphs all admit transitive metacyclic groups of automorphisms [13, 22] (such graphs are called weak metacirculants). This is what led Marušič and Šparl to initiate a systematic study of tetravalent half-arc-transitive weak metacirculants. In [15] they showed that each such graph belongs to at least one of four (non-disjoint—see [24]) classes of such graphs, where Class I coincides with the family of all tightly attached graphs. While Class II was completely classified in [23] and Class III was studied to some extent in [9], Class IV did not receive much attention thus far and seems to be the hardest one to tackle. Investigation of this class of graphs was initiated in [2] where it was proved that each member of the class belongs to a certain 8-parametric family of graphs denoted as ${{\mathcal{X}}}_{IV}(m,n;r,t;a,p;b,q)$ (see Sect. 2 for the definition). Nevertheless, the question of which members of the family are indeed half-arc-transitive and which are arc-transitive remains largely open. In an ongoing process of obtaining a better understanding of these graphs and perhaps classifying the half-arc-transitive ones [10], (another) mysterious family of arc-transitive graphs emerged. As with the above mentioned family from [13, 22] its members are all of order divisible by 42. It is thus not so surprising that there is a very large intersection of the two families. These facts thus call for a thorough investigation of these mysterious families and raise the question of the origin of arc-transitivity of their members.

In this paper we prove that, with the exception of the above mentioned graph of order 21, the members of the mysterious family from [13, 22] all belong to the above mentioned mysterious family of Class IV graphs and that they are all certain cyclic covers of the dart graph (see Sect. 2 for the definition) of the Heawood graph, the well-known incidence graph of the Fano plane. We prove that the full automorphism group of the Heawood graph naturally lifts to the automorphism groups of these graphs, which explains why their automorphism groups are rather large. We also explain the following curiosity. It turns out that the dart graph of the Heawood graph is isomorphic to the graph ${{\mathcal{X}}}_{IV}(6,7;2,0;1,0;1,1) \cong {\mathcal{X}}_{IV}(6,7;3,0;1,0;1,1)$. However, letting $m > 1$ be any integer coprime to 3 and then choosing q to be the unique integer with $0< q < m$ and $3q \equiv -1 \pmod{m}$, it turns out that the graph ${\mathcal{X}}_{IV}(6m, 7; 2, 0; 1, 0; 6q+1, 1)$ is half-arc-transitive while the graph ${\mathcal{X}}_{IV}(6m, 7; 3, 0; 1, 0; 6q+1, 1)$ is arc-transitive and belongs to the above mentioned mysterious family.

It should be mentioned that an interesting connection between the Fano plane and a natural ${\mathbb{Z}}_2$-quotient graph of ${\mathcal{X}}_{IV}(6,7;2,0;1,0;1,1) \cong {\mathcal{X}}_{IV}(6,7;3,0;1,0;1,1)$ (via so-called dichotomies) was investigated in [26].

2 Preliminaries

Throughout the paper all graphs are assumed to be finite and simple. For a graph $\Gamma = (V, E)$ and its vertex $v \in V$ we denote the set of neighbors of v in $\Gamma$ by $N_\Gamma (v)$ or simply N(v) if the graph $\Gamma$ is clear from the context. Throughout the paper we will constantly be working with elements from the ring ${\mathbb{Z}}_n$ of residue classes modulo n and its group of units ${\mathbb{Z}}_n^*$.

2.1 Symmetries of Graphs

We first review some standard terminology pertaining to symmetries of graphs. Let $\Gamma = (V,E)$ be a graph. For a subgroup $G \le{\text{Aut}}(\Gamma )$ we say that $\Gamma$ is G-vertex-transitive (G-edge-transitive, respectively) if the natural action of G on V (on E, respectively) is transitive. For a given integer $s \ge 0$ an s-arc of $\Gamma$ is a sequence of vertices of $\Gamma$ of length $s+1$ of the form $(v_0, v_1, \ldots , v_s)$ with the property that for each $0 \le i \le s-1$ we have $v_i v_{i+1} \in E$ and for each $1 \le i \le s-1$ we have $v_{i-1} \ne v_{i+1}$. The graph $\Gamma$ is said to be G-s-arc-transitive if the natural action of G on the set of all s-arcs of $\Gamma$ is transitive. Therefore, 0-arc-transitivity corresponds to vertex-transitivity. Instead of 1-arc-transitive we usually simply write arc-transitive. In the case that G acts regularly on the set of all s-arcs of $\Gamma$ we say that the group G is s-regular on $\Gamma$. Finally, if $\Gamma$ is G-vertex, G-edge, but not G-arc-transitive, we say that it is G-half-arc-transitive. In all of the above definitions we omit the prefix ${\text{Aut}}(\Gamma )$ in the case that $G ={\text{Aut}}(\Gamma )$.

We now make a short review of the concepts concerning alternating cycles and attachment sets in graphs admitting a half-arc-transitive group of automorphisms (for details, see [13]). Let $\Gamma$ be a tetravalent graph admitting a half-arc-transitive group G of automorphisms. The action of G on $\Gamma$ thus gives rise to two paired orientations of the edges of $\Gamma$ (choose an orientation of one edge and then use the action of G to define the orientation of each of the remaining edges of $\Gamma$). Fixing one of these two orientations we get an oriented graph with out-valence and in-valence both equal to 2. This gives rise to G-alternating cycles of $\Gamma$ on which every two consecutive edges are oppositely oriented. Half of the length of these cycles is called the G-radius of $\Gamma$ and is denoted by ${\text{rad}}_G(\Gamma )$. The intersections of non-disjoint G-alternating cycles are called G-attachment sets while their size is the G-attachment number of $\Gamma$ (denoted ${\text{att}}_G(\Gamma )$). In the case that ${\text{rad}}_G(\Gamma ) ={\text{att}}_G(\Gamma )$, the graph $\Gamma$ is said to be tightly G-attached. In all of the above terminology the prefix ${\text{Aut}}(\Gamma )$ is omitted when $G ={\text{Aut}}(\Gamma )$.

Let $\Gamma$ be a graph of order mn. An automorphism $\alpha$ of $\Gamma$ is said to be (m, n)-semiregular if the group $\langle \alpha \rangle$ has m orbits of length n in its natural action on the vertex-set of $\Gamma$. If a graph $\Gamma$ admits a semiregular automorphism $\rho$ and another automorphism $\sigma$, normalizing $\rho$, such that the metacyclic group $\langle \rho , \sigma \rangle$ is vertex-transitive, the graph $\Gamma$ is said to be a weak metacirculant [15]. A tetravalent weak metacirculant $\Gamma$ admitting a half-arc-transitive group of automorphisms is said to be of Class IV [15] if it admits a transitive metacyclic group $\langle \rho , \sigma \rangle$ such that each vertex of $\Gamma$ has its four neighbors in four different orbits of the subgroup generated by the semiregular automorphism $\rho$. In [2] it was shown that each such graph belongs to the following 8-parametric family of graphs.

Construction 2.1

Let $m \ge 5$ and $n \ge 3$ be integers, let $1 \le p< q < m-p$ be such that $\gcd (p,q,m) = 1$ and let $r, t, a, b \in {\mathbb{Z}}_n$ be such that $r^m = 1$, $t(r-1) = 0$ and $\langle a,b,t \rangle = {\mathbb{Z}}_n$, that is, $\gcd (a,b,t,n) = 1$. The graph ${\mathcal{X}}_{IV}(m,n;r,t;p,a;q,b)$ is then the graph with vertex set $\{ u_i^j\,:\, i \in {\mathbb{Z}}_m,\ j \in {\mathbb{Z}}_n\}$ with adjacency given by

$$\begin{aligned} u_i^j \sim{\left\{ \begin{array}{ll} u_{i+p}^{j+a r^i}, \, u_{i+q}^{j+b r^i} &{} : \quad 0\le i<m-q, j\in {\mathbb {Z}}_n, \\ u_{i+p}^{j+a r^i}, \, u_{i+q}^{j+b r^i +t} &{} : \quad m-q\le i<m-p, j\in {\mathbb {Z}}_n, \\ u_{i+p}^{j+a r^i+t}, \, u_{i+q}^{j+b r^i +t} &{} : \quad m-p\le i<m, j\in {\mathbb {Z}}_n. \\ \end{array}\right. } \end{aligned}$$

(1)

Although the above definition of the ${\mathcal{X}}_{IV}(m,n;r,t;p,a;q,b)$ graphs requires $p< q < m-p$, we make an agreement to abuse this notation a bit in this paper and allow $1 = p = q$ while still keeping the adjacencies from (1).

2.2 Consistent Cycles

When studying graphs possessing a considerable degree of symmetry the concept of consistent cycles proves to be very useful. This notion was introduced by Conway in 1971 and has been generalized [3, 16, 17] and successfully applied in the study of symmetry properties of graphs several times in the last decade. Consistent cycles also play a key role in one of the two constructions of tetravalent graphs admitting a half-arc-transitive group of automorphisms presented in this paper. We therefore recall the basic definitions and the result on the number of orbits of directed consistent cycles in an arc-transitive graph.

Let $\Gamma$ be a graph admitting an arc-transitive group of automorphisms $G \le{\text{Aut}}(\Gamma )$. In what follows we will be working with directed cycles which we think of as connected subgraphs of valence 2 together with one of the two possible orientations. We represent a directed cycle of length s with any one of the s cyclic rotations of the sequence of its s vertices, given in the order of the prescribed orientation as they appear on the cycle. Therefore, the directed cycle $\vec{C} = (v_0,v_1,\ldots , v_{s-1})$ is equal to its “shift” $(v_1, v_2, \ldots , v_{s-1}, v_0)$, but not to its reverse $\vec{C}^{-1} = (v_0,v_{s-1},v_{s-2}, \ldots , v_1)$. A directed cycle $\vec{C} = (v_0,v_1,\ldots , v_{s-1})$ of $\Gamma$ is said to be G-consistent if there exists an automorphism $\alpha \in G$ mapping each $v_i$ to $v_{i+1}$ (where the indices are computed modulo s). In this case $\alpha$ is said to be a shunt of $\vec{C}$. Of course, the reverse cycle $\vec{C}^{-1}$ is G-consistent if and only if $\vec{C}$ is G-consistent. This is why an (undirected) cycle is said to be G-consistent if both of its two corresponding directed cycles are G-consistent.

Suppose $\vec{C}$ is a G-consistent directed cycle. It may happen that there is an automorphism in G, mapping $\vec{C}$ to $\vec{C}^{-1}$. In such a case we say that the underlying undirected cycle C of $\vec{C}$ is a G-symmetric consistent cycle. Otherwise it is a G-chiral consistent cycle. It is well known and easy to see that G induces a natural action on the set of all G-consistent (directed) cycles of $\Gamma$. The above remarks imply that each G-orbit of G-symmetric consistent cycles corresponds to one G-orbit of G-consistent directed cycles, while each G-orbit of G-chiral consistent cycles corresponds to two G-orbits of G-consistent directed cycles. Moreover, the following result [17, Corollary 5.2] is now well known.

Proposition 2.2

[17] Let $\Gamma$ be a regular k-valent graph admitting an arc-transitive group of automorphisms $G \le{\text{Aut}}(\Gamma )$ and let s and c denote the numbers of G -orbits of G-symmetric and G-chiral consistent cycles, respectively. Then $s+2c = k-1$.

In Sect. 3 we will be dealing with a very specific situation where the graph $\Lambda$ under consideration will be cubic and there will exist a 1-regular subgroup $G \le{\text{Aut}}(\Lambda )$. In this case Proposition 2.2 implies that $\Lambda$ has two G-orbits of G-consistent directed cycles. Moreover, as G is 1-regular, no element of G can map a cycle to its reverse (as no element of G can fix a vertex and interchange two of its neighbors—it would have to fix the third neighbor). This implies the following useful observation (see also [16, Corollary 2.3]).

Lemma 2.3

Let $\Lambda$ be a cubic graph admitting a 1-regular group of automorphisms $G \le{\text{Aut}}(\Lambda )$. Then $\Lambda$ has just one G-orbit of G-consistent cycles which are thus G-chiral. Moreover, for any 2-arc (u, v, w) of $\Lambda$ there is a unique G-consistent directed cycle $\vec{C}$ passing through it, whose orientation is consistent with (u, v, w). In addition, the unique G -consistent directed cycle passing through the reverse 2-arc (w, v, u), whose orientation is consistent with (w, v, u), is the reverse $\vec{C}^{-1}$ of $\vec{C}$ which is not contained in the same G-orbit of G -consistent directed cycles of $\Lambda$ as $\vec{C}$.

2.3 Graph Covers

The results concerning lifts of automorphisms in (regular) graph covers are among the most frequently used results in papers dealing with graph symmetries. The main theory was developed two decades ago (see for instance [11, 12]), and so most concepts and important results are well known. We therefore omit basic definitions and only briefly recall the most important concepts. We also recall a necessary and sufficient condition under which a given automorphism of the base graph lifts along a regular covering projection that will be important for us. The reader is referred to [11, 12] for details.

It is well known that every covering projection $\wp :\Gamma ' \rightarrow \Gamma$ can be described in terms of a voltage assignment $\zeta$ which is a mapping from the set of the arcs of $\Gamma$ to a given group acting on a set, called the abstract fibre. In the case that this action is the (left) regular representation of the group under consideration we speak of a regular voltage assignment. For the sake of completeness we recall how the corresponding derived graph is constructed in such a situation. For simplicity we restrict to covers of simple graphs here. Let $\Gamma = (V,E)$ be a graph and let $\zeta :A(\Gamma ) \rightarrow R$ be a voltage assignment, where $A(\Gamma )$ is the set of arcs of $\Gamma$, R is a group and $\zeta ((u,v)) = (\zeta ((v,u)))^{-1}$ holds for all $(u,v) \in A(\Gamma )$. The derived graph ${\text{Cov}}(\Gamma , R, \zeta )$ is then the graph with vertex set $V \times R$ in which for each edge uv of $\Gamma$ and each $r \in R$ the vertex (u, r) is adjacent to $(v, \zeta ((u,v)) r)$. Observe that in this way the group R has a natural semiregular (right) action on the graph ${\text{Cov}}(\Gamma , R, \zeta )$ given by multiplication of the second component.

To state the result from [11] giving a necessary and sufficient condition for an automorphism of the base graph $\Gamma$ to lift to the derived graph ${\text{Cov}}(\Gamma , R, \zeta )$ we need just one more definition. Given a voltage assignment $\zeta :A(\Gamma ) \rightarrow R$ and a walk $W = (v_0, v_1, \ldots , v_s)$ we let the voltage $\zeta (W)$ of W be the product $\zeta ((v_{s-1}, v_s))\zeta ((v_{s-2}, v_{s-1})) \cdots \zeta ((v_0, v_1))$. Moreover, for an automorphism $\alpha$ of $\Gamma$ we let $W^\alpha = (v_0^\alpha , v_1^\alpha , \ldots , v_s^\alpha )$.

Proposition 2.4

[11, Corollary 4.3] Let $\Gamma$ be a graph, let R be an abelian group with additive operation and let $\zeta :A(\Gamma ) \rightarrow R$ be a regular voltage assignment. Then an automorphism $\alpha$ of $\Gamma$ lifts to the derived graph ${\text{Cov}}(\Gamma , R, \zeta )$ if and only if for every closed walk W we have that $\zeta (W) = 0$ if and only if $\zeta (W^\alpha ) = 0$.

2.4 The Dart Graph Construction

Before we can start describing our two constructions of covers we need to review one more concept. In [8] Hill and Wilson introduced two constructions that, given a cubic graph admitting a large enough degree of symmetry, produce a tetravalent vertex- and edge-transitive graph. In this paper we will be interested in one of their constructions, namely the dart graph construction (we remark that this construction can also be viewed as a special kind of the arc graph construction from [7]). We recall the definition and some basic properties of the construction here, but see [8, 19] for more details.

Let $\Lambda$ be a cubic graph and let $A(\Lambda )$ be the set of its arcs. The dart graph ${\text{D}}(\Lambda )$ of $\Lambda$ is then the graph with vertex set $A(\Lambda )$ in which vertices (u, v) and (x, y) are adjacent whenever either $v = x$ and $u \ne y$ or $u = y$ and $v \ne x$. In other words, we require (u, v) and (x, y) to form a 2-arc of $\Lambda$. Of course, each automorphism of $\Lambda$ has a natural action on ${\text{D}}(\Lambda )$ and ${\text{D}}(\Lambda )$ also admits the canonical involution $\tau$, interchanging each (u, v) with its reverse (v, u), as an automorphism. It was proved in [8] that the dart graph ${\text{D}}(\Lambda )$ of a cubic graph $\Lambda$ is bipartite if and only if $\Lambda$ is bipartite and that (with the above mentioned natural embedding of ${\text{Aut}}(\Lambda )$ into ${\text{Aut}}({\text{D}}(\Lambda ))$) we have that ${\text{Aut}}({\text{D}}(\Lambda )) ={\text{Aut}}(\Lambda ) \times \langle \tau \rangle$, unless $\Lambda$ is the graph of the cube. Moreover, it was proved that ${\text{D}}(\Lambda )$ is half-arc-transitive if and only if ${\text{Aut}}(\Lambda )$ is 1-regular, while ${\text{D}}(\Lambda )$ is arc-transitive if and only if ${\text{Aut}}(\Lambda )$ is at least 2-arc-transitive. We also recall the following result from [19].

Proposition 2.5

[19, Theorem 3] Let $\Gamma$ be a connected tetravalent graph. Then $\Gamma$ is G-half-arc-transitive for some $G \le{\text{Aut}}(\Gamma )$ with ${\text{rad}}_G(\Gamma ) = 3$ and ${\text{att}}_G(\Gamma ) = 2$ if and only if $\Gamma ={\text{D}}(\Lambda )$ for some 2-arc-transitive cubic graph $\Lambda$.

3 The Two Constructions

Throughout this section let $\Lambda$ be a connected cubic bipartite and vertex-transitive graph. We first present a construction of cyclic covers of the dart graph ${\text{D}}(\Lambda )$ of $\Lambda$ such that all the (natural) automorphisms of ${\text{D}}(\Lambda )$ lift. As we show in Theorem 3.3, the corresponding covers admit a half-arc-transitive group of automorphisms relative to which they are loosely-attached with radius 3, provided that the graph $\Lambda$ is at least 2-arc-transitive.

Construction 3.1

Let $m \ge 1$ be an integer and let $\Lambda$ be a connected cubic bipartite and vertex-transitive graph. Let $V(\Lambda ) = V_0 \cup V_1$ be the bipartition of its vertices. We say that the vertices from $V_0$ are white while those from $V_1$ are black. Let $\Gamma ={\text{D}}(\Lambda )$ be the dart graph of $\Lambda$. Orient the edges of $\Gamma$ in the natural way, that is, the edge (u, v)(v, w) of $\Gamma$, where u and w are two distinct neighbors of v in $\Lambda$, is oriented from (u, v) to (v, w). This edge is said to be white or black depending on whether v is white or black, respectively. Finally, assign voltage $0 \in {\mathbb{Z}}_m$ to all the arcs of $\Gamma$, corresponding to the white edges of $\Gamma$, and assign voltage 1 or $-1$ in ${\mathbb{Z}}_m$ to the arcs corresponding to the black edges of $\Gamma$, depending on whether their direction is consistent with the above mentioned natural orientation or not, respectively. The corresponding derived graph of $\Gamma$ with respect to this voltage assignment in ${\mathbb{Z}}_m$ is denoted by ${\mathcal{C}}_{{\text{D}}}^b(\Lambda , m)$, where the symbol ${\text{D}}$ indicates that we are making covers of ${\text{D}}(\Lambda )$ and b indicates that we require $\Lambda$ to be bipartite.

Fig. 1

The graph ${\text{D}}(K_{3,3})$ with the arcs carrying voltage 1 indicated by arrows

We first show that the graph ${\mathcal{C}}_{{\text{D}}}^b(\Lambda , m)$ from the above construction is well defined.

Lemma 3.2

Use the assumptions and notation from Construction 3.1. Then, up to isomorphism, the graph ${\mathcal{C}}_{{\text{D}}}^b(\Lambda ,m)$ does not depend on the choice of which part of the bipartition of $V(\Lambda )$ is considered as the set of white vertices and which as the set of black vertices.

Proof

Since the graph $\Lambda$ is assumed to be vertex-transitive, there exists an automorphism $\alpha$ of $\Lambda$ exchanging the sets $V_0$ and $V_1$, and so exchanging the roles of $V_0$ and $V_1$ in Construction 3.1 results in an isomorphic graph. $\square$

In Fig. 1 the dart graph of the complete bipartite graph $K_{3,3}$ together with the indication of which arcs receive voltage 1 (the corresponding arcs have arrows) is depicted. The reader will observe that, since $\Lambda$ is bipartite, its dart graph ${\text{D}}(\Lambda )$ has white 6-cycles (which consist of 6 white edges) corresponding to the white vertices of $\Lambda$, and black 6-cycles corresponding to the black vertices of $\Lambda$. This simple observation can be of help when one considers the automorphism group of ${\text{D}}(\Lambda )$ and of ${\mathcal{C}}_{\text{D}}^b(\Lambda , m)$. We now determine some properties of the covers ${\mathcal{C}}_{\text{D}}^b(\Lambda , m)$.

Theorem 3.3

Let $\Lambda$ be a connected cubic bipartite and vertex-transitive graph, let $m > 1$ be an integer and let $\Gamma _m = {\mathcal{C}}_{{\text{D}}}^b(\Lambda , m)$ from Construction 3.1. Then $\Gamma _m$ is a connected bipartite tetravalent graph. Moreover, the natural subgroup ${\text{Aut}}(\Lambda ) \times \langle \tau \rangle$ of ${\text{Aut}}({\text{D}}(\Lambda ))$, where $\tau$ is the canonical involution interchanging each vertex (u, v) of ${\text{D}}(\Lambda )$ with (v, u), lifts to ${\text{Aut}}(\Gamma _m)$. In particular, if $G \le{\text{Aut}}(\Lambda )$ is s-arc-regular for some $s \ge 2$, then $\Gamma _m$ is an arc-transitive graph admitting a half-arc-transitive group of automorphisms with vertex stabilizers of order $2^{s-1}$, relative to which the radius is 3 and the attachment number is 1.

Proof

Throughout the proof we adopt the notation and terminology from Construction 3.1. Since $\Lambda$ is bipartite, so is ${\text{D}}(\Lambda )$ (simply call the vertex (u, v) white or black depending on whether u is white or black, respectively), and so $\Gamma _m$ is also bipartite. We proceed by proving a series of claims.

Claim 1 $\Gamma _m$ is connected.

Connectedness of $\Lambda$ ensures that ${\text{D}}(\Lambda )$ is connected, and so it suffices to prove that for a vertex (u, v) of ${\text{D}}(\Lambda )$ there is a closed walk at (u, v) in ${\text{D}}(\Lambda )$ with voltage 1. Since $\Lambda$ is cubic $N_\Lambda (v) \setminus \{u\} = \{x_1, x_2\}$ for some $x_1$ and $x_2$, and similarly $N_\Lambda (u) \setminus \{v\} = \{y_1, y_2\}$ for some $y_1$ and $y_2$. The closed walk $((u,v),(v,x_1),(x_2,v),(v,u),(u,y_1),(y_2,u),(u,v))$ consists of three consecutive edges of one color and then three consecutive edges of the other color. Regardless of whether u is white or black the first black edge on this walk is traversed in the direction that carries voltage 1, and so the voltage of this walk is $1-1+1=1$, completing the proof of Claim 1.

To analyze the automorphisms of ${\text{D}}(\Lambda )$ that lift to ${\text{Aut}}(\Gamma _m)$ we first introduce the following additional notation, which is based on the distinction of white and black edges of ${\text{D}}(\Lambda )$ from Construction 3.1. For each walk W in ${\text{D}}(\Lambda )$ let the white weight $\zeta _0(W)$ of W be the number of white edges of W traversed in the direction of their natural orientation in ${\text{D}}(\Lambda )$, minus the number of white edges of W traversed against their natural orientation in ${\text{D}}(\Lambda )$. The black weight $\zeta _1(W)$ of W is defined analogously.

Claim 2 For each walk W in ${\text{D}}(\Lambda )$ we have that

$$\begin{aligned} |\zeta _0(W) - \zeta _1(W)| = \left\{ \begin{array}{ccc} 0 & : &\quad |W| {\text{even}}\\ 1 & : &\quad |W| {\text {odd}}.\end{array}\right. \end{aligned}$$

We prove the claim by induction on the length of W. For trivial walks and walks of length 1 the claim clearly holds. Suppose now that W is a walk of length 2 in ${\text{D}}(\Lambda )$. Observe that each vertex of ${\text{D}}(\Lambda )$ is incident to two white and two black edges and that with respect to the natural orientation of the edges of ${\text{D}}(\Lambda )$ the white and black 6-cycles are alternating. It thus follows that in the case that the two edges of W are of the same color, $\zeta _0(W) = \zeta _1(W) = 0$ holds. If however the two edges of W are of different colors, then on W they are either both traversed with the natural orientation or both against it. Since one is white and the other is black it follows that $\zeta _0(W) = \zeta _1(W)$, and so our claim holds for all walks of length at most 2. Using induction on the length of W it now easily follows that the claim holds for all walks. Namely, let W be a walk of length $d \ge 3$. Split the walk W into walks $W_1$ and $W_2$, where $W_2$ consists of the last two edges of W. Since $\zeta _0(W) = \zeta _0(W_1) + \zeta _0(W_2)$ and $\zeta _1(W) = \zeta _1(W_1) + \zeta _1(W_2)$, the fact that $\zeta _0(W_2) = \zeta _1(W_2)$ implies that $|\zeta _0(W) - \zeta _1(W)| = |\zeta _0(W_1) - \zeta _1(W_1)|$, and so we can apply the induction hypothesis. This proves Claim 2.

Claim 3 For each $\gamma \in{\text{Aut}}(\Lambda )$ the corresponding automorphism of ${\text{D}}(\Lambda )$ lifts to ${\text{Aut}}(\Gamma _m)$.

Let $\gamma \in{\text{Aut}}(\Lambda )$ be an automorphism of $\Lambda$. Abusing the notation a bit we let the natural action of $\gamma$ on ${\text{D}}(\Lambda )$ again be denoted by $\gamma$. Proposition 2.4 implies that $\gamma$ lifts to ${\text{Aut}}(\Gamma _m)$ if and only if the set of all closed walks in ${\text{D}}(\Lambda )$ with voltage 0 is preserved by $\gamma$. Observe that $\zeta (W) = \zeta _1(W)$ for any walk W in ${\text{D}}(\Lambda )$. Since ${\text{D}}(\Lambda )$ is bipartite, any closed walk W in ${\text{D}}(\Lambda )$ is of even length, and so Claim 2 shows that $\zeta (W) = 0$ if and only if $\zeta _0(W) = 0$. Now, $\gamma$ preserves the natural orientation of the edges of ${\text{D}}(\Lambda )$ and it either fixes setwise the set of all white edges of ${\text{D}}(\Lambda )$ or interchanges it with the set of all black edges of ${\text{D}}(\Lambda )$. It thus follows that $\zeta (W) = 0$ if and only if $\zeta (W^\gamma ) = 0$, proving that $\gamma$ lifts to ${\text{Aut}}(\Gamma _m)$, as claimed.

Claim 4 The natural subgroup ${\text{Aut}}(\Lambda ) \times \langle \tau \rangle$ of ${\text{Aut}}({\text{D}}(\Lambda ))$ lifts to ${\text{Aut}}(\Gamma _m)$.

In view of Claim 3 it suffices to show that the canonical involution $\tau$ lifts to ${\text{Aut}}(\Gamma _m)$. But as $\tau$ fixes setwise the set of white edges and maps each (black) arc with voltage 1 to a (black) arc with voltage $-1$ and vice versa, $\zeta (W^\tau ) = -\zeta (W)$ holds for each walk W of ${\text{D}}(\Lambda )$. It follows that the set of all closed walks with voltage 0 is preserved by $\tau$, implying that $\tau$ lifts to ${\text{Aut}}(\Gamma _m)$.

To prove the last part of the theorem let $G \le{\text{Aut}}(\Lambda )$ be s-arc-regular on $\Lambda$ for some $s \ge 2$. By [19, Proposition 5] the natural (faithful) action of G on ${\text{D}}(\Lambda )$ is half-arc-transitive with the corresponding radius 3 and attachment number 2 (the corresponding alternating cycles are the white and black 6-cycles). Moreover, the group ${\text{Aut}}(\Lambda ) \times \langle \tau \rangle$ acts arc-transitively on ${\text{D}}(\Lambda )$. Observe that an s-arc of $\Lambda$ corresponds to an $(s-1)$-arc of ${\text{D}}(\Lambda )$ (having the direction which is consistent with the natural orientation of ${\text{D}}(\Lambda )$). The fact that vertex-stabilizers for the action of G on $\Lambda$ are of order $3\cdot 2^{s-1}$ thus implies that the vertex-stabilizers of the action of G on ${\text{D}}(\Lambda )$ are of order $2^{s-1}$. Since we have already proved that the entire group $G \le{\text{Aut}}({\text{D}}(\Lambda ))$ lifts to a subgroup $\tilde{G} \le{\text{Aut}}(\Gamma _m)$, it is now clear that the action of $\tilde{G}$ on ${\text{Aut}}(\Gamma _m)$ is half-arc-transitive with vertex-stabilizers of order $2^{s-1}$. Moreover, since the G-alternating cycles of ${\text{D}}(\Lambda )$ are precisely the white and black 6-cycles of ${\text{D}}(\Lambda )$ which all receive voltage 0, the $\tilde{G}$-radius of $\Gamma _m$ is 3. Finally, let $u, v, x_1, x_2, y_1$ and $y_2$ be as at the beginning of this proof, where we assume that v is black. Then the intersection of the G-alternating cycles of ${\text{D}}(\Lambda )$ corresponding to u and v is $\{(u,v), (v,u)\}$. But since the voltage of the walk $((u,v),(v,x_1),(x_2,v),(v,u))$ is 1, while on the other hand the voltage of the walk $((u,v),(y_1,u),(u,y_2),(v,u))$ is 0, the intersection of the lifts of these two G-alternating cycles is trivial (recall that $m > 1$). $\square$

We now describe another construction of cyclic covers of the dart graph ${\text{D}}(\Lambda )$ of a cubic bipartite and vertex-transitive graph $\Lambda$ where in this case we assume in addition that ${\text{Aut}}(\Lambda )$ contains a 1-regular group.

Construction 3.4

Let $m \ge 1$ be an integer and let $\Lambda$ be a connected cubic bipartite graph admitting a 1-regular group of automorphisms $G \le{\text{Aut}}(\Lambda )$. Let $V(\Lambda ) = V_0 \cup V_1$ be the bipartition of $V(\Lambda )$. We call the vertices from $V_0$ white and the ones from $V_1$ black. Choose one of the two paired orbits of G-consistent directed cycles of $\Lambda$ and denote it by $\mathcal{O}$. For each arc ((u, v), (v, w)) of $\Gamma = D(\Lambda )$ assign the voltage from ${\mathbb{Z}}_m$ to it as follows. If the unique G-consistent directed cycle of $\Lambda$ containing the 2-arc (u, v, w) is not contained in $\mathcal{O}$, assign voltage 0 to ((u, v), (v, w)). Otherwise, assign voltage 1 or $-1$ to ((u, v), (v, w)) according to whether v is white or black, respectively. The arc ((v, w), (u, v)) of course receives voltage $-1$, 1 or 0, according to whether ((u, v), (v, w)) receives 1, $-1$ or 0, respectively. The corresponding derived graph of $\Gamma$ with respect to this voltage assignment in ${\mathbb{Z}}_m$ is denoted by ${\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G, m)$, where ${\text{D}}$ indicates that we are making covers of the dart graph of $\Lambda$, and the pair b, 1 indicates that we require $\Lambda$ to be bipartite and G to be 1-regular on $\Lambda$.

In Fig. 2 the voltage assignment of the dart graph of $K_{3,3}$ is depicted, where we have chosen the 1-regular group $\langle (1\,3\,5), (0\,3)(1\,4)(2\,5)\rangle$ and the corresponding orbit of consistent directed cycles consisting of the 6-cycles (0, 1, 2, 3, 4, 5), (0, 3, 2, 5, 4, 1) and (0, 5, 2, 1, 4, 3). The arcs receiving voltage 1 have arrows (while those receiving voltage 0 have no arrows).

Fig. 2

A voltage assignment on ${\text{D}}(K_{3,3})$ corresponding to Construction 3.4

As with the first construction, we first show that ${\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G, m)$ does not depend on the choice of which part of the bipartition of $V(\Lambda )$ is considered as the set of white vertices, nor on the choice of the orbit $\mathcal{O}$ of G-consistent cycles of $\Lambda$.

Lemma 3.5

Use the assumptions and notation from Construction 3.4. Then, up to isomorphism, the graph ${\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G, m)$ does not depend on the choice of which part of the bipartition of $V(\Lambda )$ is considered as the set of white vertices and which as the set of black vertices, nor on the choice of the orbit of G-consistent cycles of $\Lambda$.

Proof

To see that the choice of which vertices are called white and which black is not important, observe that mapping each vertex ((u, v), i) to $((u,v),-i)$ (recall that $i \in {\mathbb{Z}}_m$) we obtain an isomorphism of graphs where we keep the chosen orbit $\mathcal{O}$ while exchanging the roles of white and black vertices. To see that the graph ${\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G, m)$ also does not depend on the choice of $\mathcal{O}$, let $\alpha \in G$ be any automorphism of $\Lambda$ interchanging the sets of white and black vertices of $\Lambda$. By Lemma 2.3 there exists a G-consistent directed cycle $\vec{C} \in \mathcal{O}$ through a given 2-arc (u, v, w) of $\Lambda$ if and only if there does not exist a G-consistent directed cycle from $\mathcal{O}$ through the 2-arc (w, v, u). Denote by $\Gamma _m$ the graph obtained from Construction 3.4 with respect to $\mathcal{O}$ and by $\Gamma _m'$ the one obtained with respect to the other orbit $\mathcal{O}'$ of G-consistent directed cycles of $\Lambda$ (the choice of which vertices of $\Lambda$ are called white is the same in both cases). Consider now the mapping from $\Gamma _m$ to $\Gamma _m'$, given by the rule:

$$\begin{aligned} ((u,v),i) \mapsto \left\{ \begin{array}{ccl} ((u^\alpha , v^\alpha ),i) &{} : &{}\quad u \in V_0\\ ((u^\alpha , v^\alpha ),i+1) &{} : &{}\quad u \in V_1.\end{array}\right. \end{aligned}$$

It is clear that this mapping is bijective. To see that it also preserves adjacency, let $(u,v) \in V({\text{D}}(\Lambda ))$ and $i \in {\mathbb{Z}}_m$. Let $w_1, w_2$ be the two neighbors of v in $\Lambda$, different from u. With no loss of generality assume there is a G-consistent directed cycle $\vec{C} \in \mathcal{O}$ through $(u,v,w_1)$ (which implies there is no directed cycle from $\mathcal{O}$ through $(u,v,w_2)$, but there is one from $\mathcal{O}'$). We consider the case when $u \in V_0$ and leave the similar case of $u \in V_1$ to the reader. Since $u \in V_0$ (and thus $v \in V_1$) and there is a cycle from $\mathcal{O}$ through $(u,v,w_1)$, we have that $((u,v),i) \sim ((v,w_1),i-1), ((v,w_2),i)$. As $u \in V_0$, the vertex ((u, v), i) is mapped to $((u^\alpha , v^\alpha ), i)$, while $((v,w_1),i-1)$ and $((v,w_2),i)$ are mapped to $((v^\alpha , w_1^\alpha ),i)$ and $((v^\alpha , w_2^\alpha ),i+1)$, respectively. Since there is a directed cycle from $\mathcal{O}$ through $(u^\alpha , v^\alpha , w_1^\alpha )$, there is no directed cycle from $\mathcal{O}'$ through $(u^\alpha , v^\alpha , w_1^\alpha )$, but there is one through $(u^\alpha , v^\alpha , w_2^\alpha )$. Thus, as $v^\alpha \in V_0$ (recall that $\alpha$ interchanges all white vertices with black ones), the above corresponding edges of $\Gamma _m$ are mapped to edges of $\Gamma _m'$. $\square$

Note that, since the graph ${\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G, m)$ is a covering graph of $D(\Lambda )$, we can again speak of white and black 6-cycles of $D(\Lambda )$. However, this time every other edge of each of these 6-cycles has trivial voltage and the total voltage of a corresponding directed 6-cycle is 3 (or $-3$, depending on the direction of the traversal of the 6-cycle). This fact can be useful in the investigation of automorphisms of ${\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G, m)$ and in fact proves the first claim of the following theorem.

Theorem 3.6

Let $\Lambda$ be a connected cubic bipartite graph admitting a 1-regular group $G \le{\text{Aut}}(\Lambda )$, let $m \ge 1$ be an integer coprime to 3, and let $\Gamma _m = {\mathcal{C}}_{{\text{D}}}^{b,1}(\Lambda , G, m)$ from Construction 3.4. Then $\Gamma _m$ is a connected bipartite tetravalent graph. Moreover, the natural subgroup $G \times \langle \tau \rangle$ of ${\text{Aut}}({\text{D}}(\Lambda ))$, where $\tau$ is the canonical involution interchanging each vertex (u, v) of ${\text{D}}(\Lambda )$ with (v, u), lifts to ${\text{Aut}}(\Gamma _m)$ and acts half-arc-transitively on $\Gamma _m$. Moreover, if H is a subgroup of ${\text{Aut}}(\Lambda )$ with $G \lneq H$ such that the subgroup of ${\text{Aut}}({\text{D}}(\Lambda ))$ corresponding to H lifts to ${\text{Aut}}(\Gamma _m)$, then $[H:G] = 2$. In other words, H is 2-regular on $\Lambda$. Conversely, if $K \le{\text{Aut}}(\Lambda )$ is such that $G \le K$ with $[K:G] = 2$, then the subgroup of ${\text{Aut}}({\text{D}}(\Lambda ))$ corresponding to K lifts to ${\text{Aut}}(\Gamma _m)$ and $\Gamma _m$ is arc-transitive.

Proof

That $\Gamma _m$ is a tetravalent bipartite graph follows from the fact that ${\text{D}}(\Lambda )$ is tetravalent and bipartite, while the fact that $\Gamma _m$ is connected was implicitly established in the paragraph preceding the statement of this proposition (recall that ${\text{D}}(\Lambda )$ is connected and that m is coprime to 3). We proceed by proving a series of claims.

Claim 1 For each $\gamma \in G$ the corresponding automorphism of ${\text{D}}(\Lambda )$ lifts to ${\text{Aut}}(\Gamma _m)$.

Let $\gamma \in G$ and, as in the proof of Theorem 3.3, let the natural action of $\gamma$ on ${\text{D}}(\Lambda )$ again be denoted by $\gamma$. Proposition 2.4 implies that it suffices to verify that $\gamma$ preserves the set of closed walks of ${\text{D}}(\Lambda )$ with trivial voltage. Since the set $\mathcal{O}$ from Construction 3.4 is a G-orbit (of G-consistent directed cycles) it is preserved by $\gamma$. Therefore, if $\gamma$ (viewed as an automorphism of $\Lambda$) preserves the set $V_0$ of white vertices of $\Lambda$, it maps each arc of ${\text{D}}(\Lambda )$ to an arc with the same voltage, and so $\zeta (W^\gamma ) = \zeta (W)$ for each walk W in ${\text{D}}(\Lambda )$. If however $\gamma$ interchanges the sets $V_0$ and $V_1$ of $\Lambda$, it maps each arc of ${\text{D}}(\Lambda )$ to an arc with the opposite voltage, and so $\zeta (W^\gamma ) = -\zeta (W)$ for each walk W in ${\text{D}}(\Lambda )$. In any case, $\gamma$ preserves the set of all closed walks with trivial voltage and thus lifts to ${\text{Aut}}(\Gamma _m)$.

Claim 2 The canonical involution $\tau$ lifts to ${\text{Aut}}(\Gamma _m)$.

It clearly suffices to prove that $\zeta (W) = \zeta (W^\tau )$ for any walk W of length 2 (recall that ${\text{D}}(\Lambda )$ is bipartite, implying that all closed walks are of even length). Now, observe that $\tau$ interchanges the set of arcs of ${\text{D}}(\Lambda )$ with trivial voltage with the set of arcs of ${\text{D}}(\Lambda )$ with nontrivial voltage. Moreover, by construction any walk of length 2, both of whose corresponding arcs have a nontrivial voltage, has total voltage 0. To prove the above claim regarding the walks of length 2 it thus suffices to consider walks W of length 2 with $\zeta (W) \in \{\pm 1\}$. There are two essentially different types of such walks, namely the ones for which the two edges belong to a single 6-cycle corresponding to a vertex of $\Lambda$, and the ones where the two edges belong to different 6-cycles corresponding to vertices of $\Lambda$. The walks of the first type are easy to deal with as $\tau$ acts as a 3-step rotation on each of the 6-cycles of ${\text{D}}(\Lambda )$ corresponding to vertices of $\Lambda$, and so we can simply use the remark from the paragraph preceding the statement of Theorem 3.6. As for the walks of the second kind we consider one such possibility and leave the others to the reader. Suppose $W = ((u,v),(v,w),(w,x))$ with $\zeta ((u,v),(v,w)) = 1$ and $\zeta ((v,w),(w,x)) = 0$. By definition $v \in V_0$, there is a directed cycle from $\mathcal{O}$ through (u, v, w) and there is no directed cycle from $\mathcal{O}$ through (v, w, x). Since this implies there is no directed cycle from $\mathcal{O}$ through (w, v, u) while there is one through (x, w, v), it thus follows that $\zeta ((v,u),(w,v)) = 0$ and $\zeta ((x,w),(w,v)) = -1$ (note that $w \in V_1$). Consequently, $\zeta ((w,v),(x,w)) = 1$, and so $\zeta (W^\tau ) = 1 = \zeta (W)$. As said, we leave the other possibilities for walks W of length 2 with $\zeta (W) \in \{\pm 1\}$ of the second kind to the reader. The automorphism $\tau$ thus preserves the voltage of any closed walk, and thus lifts to ${\text{Aut}}(\Gamma _m)$, as claimed.

Claims 1 and 2 thus ensure that the natural subgroup $G \times \langle \tau \rangle$ of ${\text{Aut}}({\text{D}}(\Lambda ))$ lifts to ${\text{Aut}}(\Gamma _m)$. Clearly, the action of this lift on $\Gamma _m$ is half-arc-transitive. To prove the last part of the theorem let H be a subgroup of ${\text{Aut}}(\Lambda )$ containing G such that the corresponding subgroup of ${\text{Aut}}({\text{D}}(\Lambda ))$ lifts to ${\text{Aut}}(\Gamma _m)$.

Claim 3 The action of H on $\Lambda$ is at most 2-arc-transitive.

By way of contradiction suppose H acts 3-arc-transitively on $\Lambda$ and let $v \in V_0$ be a white vertex of $\Lambda$, let $N(v) = \{u,w,x\}$ and let $N(w) \setminus \{v\} = \{y_1,y_2\}$. Since $\Lambda$ is bipartite the vertices $u,v,w,x,y_1,y_2$ are pairwise distinct. With no loss of generality assume that each of the 2-arcs (u, v, w) and $(v,w,y_1)$ lies on a directed cycle from $\mathcal{O}$. Since H acts 3-arc-transitively on $\Lambda$, there is an automorphism $\eta \in H$ fixing pointwise each of u, v and w (and thus also x) but interchanging $y_1$ with $y_2$. In the natural action of $\eta$ on ${\text{D}}(\Lambda )$ the 6-cycle $((w,v),(v,x),(u,v),(v,w),(w,y_1),(y_2,w))$, which has voltage 0, is thus mapped to the 6-cycle $((w,v),(v,x),(u,v),(v,w),(w,y_2),(y_1,w))$, which has voltage 3. Since $m \ne 3$, the automorphism $\eta$ of $D(\Lambda )$ thus maps a closed walk with trivial voltage to a closed walk with a nontrivial voltage, which contradicts Proposition 2.4. This shows that the group H indeed acts at most 2-arc-transitively on $\Lambda$, and consequently $[H:G] \le 2$.

Finally, suppose that there exists a subgroup K of ${\text{Aut}}(\Lambda )$ with $G \le K$ and $[K:G] = 2$. Then K acts regularly on the set of 2-arcs of $\Lambda$ and G is a normal subgroup of K. Denote the two G-orbits of G-consistent directed cycles of $\Lambda$ by $\mathcal{O}$ and $\mathcal{O}'$ and recall that the reverse of each directed cycle from $\mathcal{O}$ is in $\mathcal{O}'$ and vice versa.

Claim 4 $\mathcal{O}\cup \mathcal{O}'$ is a single K-orbit of K-consistent directed cycles of $\Lambda$.

Since K acts regularly on the set of 2-arcs of $\Lambda$ and $[K:G] = 2$, the group G has two orbits on the set of 2-arcs of $\Lambda$, say $\mathcal{A}$ and $\mathcal{A}'$, and each $\beta \in K \setminus G$ interchanges $\mathcal{A}$ and $\mathcal{A}'$. Observe that, as G is 1-regular, for any 2-arc $(x,y,z) \in \mathcal{A}$, letting w be the unique neighbor of y, different from x and z, the 2-arcs (z, y, x), (x, y, w), (w, y, z) all belong to $\mathcal{A}'$. Consider now a G-consistent directed cycle, say $\vec{C} = (v_0, v_1, \ldots , v_{\ell -1})$. Since $\vec{C}$ is G-consistent, there is a shunt $\alpha \in G$, mapping each $v_i$ to $v_{i+1}$, where indices are computed modulo $\ell$. It thus follows that the 2-arcs $(v_i,v_{i+1},v_{i+2})$, $i \in {\mathbb{Z}}_\ell$, are all in the same G-orbit. With no loss of generality assume they are in $\mathcal{A}$. Since K acts 2-arc-transitively on $\Lambda$ there exists $\beta \in K$ fixing $v_0$ and interchanging $v_1$ and $v_{\ell -1}$. As $(v_1,v_0,v_{\ell -1}) \in \mathcal{A}'$, $\beta$ interchanges $\mathcal{A}$ and $\mathcal{A}'$, and so the argument from the first part of this paragraph shows that $\beta$ maps $\vec{C}$ to its reverse $\vec{C}^{-1}$. It now follows that $\beta$ interchanges $\mathcal{O}$ and $\mathcal{O}'$, which finally proves Claim 4.

To see that K lifts to ${\text{Aut}}(\Gamma _m)$ let $\beta \in K$ be such that it preserves the set of white vertices of $\Lambda$ but interchanges the two G-orbits of G-consistent directed cycles of $\Lambda$ (and thus also the two G-orbits of 2-arcs of $\Lambda$). It is not difficult to verify that then $\beta \tau$ preserves the set of arcs with trivial voltage and interchanges the set of arcs with voltage 1 with the set of arcs with voltage $-1$. Consequently, $\beta \tau$ preserves the set of closed walks with trivial voltage. Therefore, $\beta$ and thus also all of K lifts to ${\text{Aut}}(\Gamma _m)$. Since K acts 2-arc-transitively on $\Lambda$, it is clear that $K \times \langle \tau \rangle$ acts arc-transitively on $D(\Lambda )$, and so the lift of $K \times \langle \tau \rangle$ to ${\text{Aut}}(\Gamma _m)$ also acts arc-transitively on $\Gamma _m$. $\square$

The above theorem gives a nice tool enabling a search for new half-arc-transitive tetravalent graphs. Namely, if we take any connected bipartite cubic graph $\Lambda$ admitting a 1-regular group $G \le{\text{Aut}}(\Lambda )$ which is not contained in some 2-regular subgroup of ${\text{Aut}}(\Lambda )$, then by Theorem 3.6 the graph ${\mathcal{C}}_{{\text{D}}}^{b,1}(\Lambda , G, m)$, where m is coprime to 3, is a good candidate for a tetravalent half-arc-transitive graph (the only thing that could prevent it from being half-arc-transitive are potential “unexpected automorphisms” that do not come from ${\text{Aut}}({\text{D}}(\Lambda ))$). One may thus use the results of [5], where the 17 types of cubic arc-transitive graphs were characterized, to make the search for potential good candidates for $\Lambda$ easier. The following straightforward observation may also be of use (in what follows we say that a subgroup G of a group K is self-normalizing in K if G equals its normalizer in K).

Lemma 3.7

Let $\Lambda$ be a cubic graph admitting a 1-regular group $G \le{\text{Aut}}(\Lambda )$. Then G is not contained in a 2-regular subgroup of ${\text{Aut}}(\Lambda )$ if and only if G is self-normalizing in ${\text{Aut}}(\Lambda )$.

Proof

If G is a subgroup of some 2-regular group K, then of course $[K:G] = 2$, and so G is not self-normalizing in ${\text{Aut}}(\Lambda )$. Conversely, suppose G is a proper subgroup of its normalizer K in ${\text{Aut}}(\Lambda )$. Then K acts transitively on the set of all 2-arcs of $\Lambda$ and since G is normal in K, the two G-orbits on 2-arcs of $\Lambda$ are blocks of imprimitivity for the action of K on this set. If K was 3-arc-transitive then one could fix a given 2-arc (x, y, z) (and thus fix setwise the two G-orbits on 2-arcs) while interchanging the two neighbors (say $w_1$ and $w_2$) of z, different from y. As $(y,z,w_1)$ and $(y,z,w_2)$ are in different G-orbits, this is impossible, showing that $[K:G] = 2$, so that G is contained in some 2-regular subgroup of ${\text{Aut}}(\Lambda )$. $\square$

Determining whether the obtained covering graph ${\mathcal{C}}_{{\text{D}}}^{b,1}(\Lambda , G, m)$, where G is a self-normalizing 1-regular subgroup of ${\text{Aut}}(\Lambda )$, admits any “unexpected” automorphisms which do not come from ${\text{D}}(\Lambda )$, may of course in general be a difficult question. Nevertheless, it seems reasonable to expect that this construction will most often result in a half-arc-transitive graph. Some evidence that this might indeed be the case can be obtained by simply taking the graphs from the list of all cubic arc-transitive graphs up to order 2048 constructed by Conder [4], filter out the bipartite ones of the appropriate types and then construct all corresponding covers as in Construction 3.4 for small values of m and check whether they are half-arc-transitive or not. Using a computer, all suitable cubic arc-transitive graphs up to order 80 (in the notation from [4] they are C14.1, C26.1, C38.1, C42.1, C56.1, C62.1, C74.1 and C78.1) were checked for all $m < 30$, coprime to 3. It turned out that all of the constructed covers are half-arc-transitive (see the next section where all such covers, regardless of the value of m, are considered for the Heawood graph C14.1). Moreover, for each of these suitable cubic graphs (except for C56.1) almost all of the constructed covers are tightly-attached, but not all. There are thus some interesting questions to consider here.

Question 3.8

If $\Lambda$ is a connected bipartite cubic graph admitting a self-normalizing 1-regular subgroup G of ${\text{Aut}}(\Lambda )$, is it true that for any $m \ge 1$ coprime to 3 the graph ${\mathcal{C}}_{{\text{D}}}^{b,1}(\Lambda , G, m)$ is half-arc-transitive? If this is not always the case, can we classify all triples $(\Lambda , G, m)$ where the resulting graph is arc-transitive?

Question 3.9

Suppose $\Lambda$ is a connected bipartite cubic graph admitting a self-normalizing 1-regular subgroup G of ${\text{Aut}}(\Lambda )$ and let $m \ge 1$ be coprime to 3 and such that the graph ${\mathcal{C}}_{{\text{D}}}^{b,1}(\Lambda , G, m)$ is half-arc-transitive. What can be said about the radius and the attachment number of this graph?

Of course, something can be said about Question 3.9, as one can easily show that the corresponding alternating cycles in ${\text{D}}(\Lambda )$ are obtained by starting with a given arc corresponding to a 2-arc (x, y, z) of $\Lambda$ and then at each next step continue along the arc corresponding to the unique 2-arc (y, z, w) of $\Lambda$ such that (x, y, z) and (y, z, w) are in different G-orbits of 2-arcs on $\Lambda$ (in other words, we never follow the current G-consistent directed cycle of $\Lambda$). Also, the voltage of such an alternating cycle can be seen to equal the radius of the cycle (and thus of ${\text{D}}(\Lambda )$). But in order not to make this paper any longer, we do not pursue these questions here but instead focus on the covers of the Heawood graph obtained by our two constructions.

4 The graphs arising from the Fano plane

In this section we apply the results from the previous section to the Heawood graph, the well-known incidence graph of the Fano plane. Both the Fano plane and the Heawood graph, as well as most of their properties are well known, but since they play a central role in this section we provide some details.

4.1 The Fano Plane and the Heawood Graph

In this paper we work with the following definition of the Fano plane. Its point-set and its line-set consist of the 7 nonzero vectors in ${\mathbb{Z}}_2^3$, where the points are written as triples (i, j, k) and the lines as triples [i, j, k]. The point (i, j, k) is then incident to the line $[i',j',k']$ whenever the corresponding scalar product is 0, that is when $ii' +jj' + kk' = 0$ (in ${\mathbb{Z}}_2$). The resulting incidence structure is depicted on the left-hand side of Fig. 3.

The Heawood graph, denoted throughout Sect. 4 by $\Lambda$, is defined as the incidence graph (also called the Levi graph [6]) of the Fano plane. It is well known that the Heawood graph is a cubic bipartite graph of order 14, diameter 3 and girth 6, and that its automorphism group acts 4-arc-transitively on it and is isomorphic to a semidirect product of ${\text{GL}}(3,2)$ by ${\mathbb{Z}}_2$ (which is isomorphic to ${\text{PGL}}(2,7)$). The group ${\text{GL}}(3,2)$ has the following natural action on the Fano plane (and thus on the Heawood graph). For a matrix $A \in{\text{GL}}(3,2)$ its action on the set of points of the Fano plane is given by multiplication by $A^{-T}$ (the transpose of the inverse matrix $A^{-1}$) and its action on the set of lines by multiplication by A. More precisely, for a point (i, j, k) and a line [i, j, k] of the Fano plane we set

$$\begin{aligned} (i,j,k) \bullet A = (i,j,k)A^{-T} \quad{\text{and}} \quad [i,j,k] \bullet A = [i, j, k]A. \end{aligned}$$

Throughout the rest of this section we shorten the notation for points and lines of the Fano plane—instead of (i, j, k) and [i, j, k] we simply write (ijk) and [ijk], respectively. We also make the agreement that the vertices of $\Lambda$ corresponding to points of the Fano plane are black, while the ones corresponding to lines of the Fano plane are white.

To illustrate the above described action of ${\text{GL}}(3,2)$ on the Fano plane and $\Lambda$ let

$$\begin{aligned} R = \left[ \begin{array}{ccc} 1 &{}\quad 1 &{}\quad 1 \\ 1 &{}\quad 0 &{}\quad 0 \\ 1 &{}\quad 0 &{}\quad 1 \end{array}\right] \quad{\text{and}} \quad B = \left[ \begin{array}{ccc} 0 &{}\quad 0 &{}\quad 1 \\ 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 1 &{}\quad 0\end{array}\right] . \end{aligned}$$

(2)

Then R moves the point (001) to the point (011) and the line [001] to the line [101], while B moves the point (001) to the point (010) and the line [001] to the line [010].

Fig. 3

The Fano plane and its incidence graph—the Heawood graph

We denote the automorphism of the Fano plane (as well as the corresponding automorphism of $\Lambda$) corresponding to R by $\rho$. The reader will notice that the action of $\rho$ on $\Lambda$ corresponds to the 2-step clockwise rotation in the presentation of $\Lambda$ as given on the right-hand side of Fig. 3. The polarity $\pi$ of the Fano plane, interchanging each point (ijk) with the line [ijk], of course preserves incidence and is thus also an automorphism of $\Lambda$ (it corresponds to the reflection of the presentation of $\Lambda$ from the right-hand side of Fig. 3 with respect to the line through the midpoint of the edge (101)[101] and the midpoint of the edge (100)[110]). It is easy to see that $\pi \rho \pi = \rho ^{-1}$. Let $\beta$ be the automorphism corresponding to the matrix B from (2). Since $B^{-T} = B$, it follows that $\pi \beta = \beta \pi$, and so $\sigma = \pi \beta$ is of order 6. One can also verify that $\beta ^{-1}\rho \beta = \rho ^4$, and so

$$\begin{aligned} \sigma ^{-1} \rho \sigma = \rho ^3. \end{aligned}$$

(3)

The group $G_1 = \langle \rho , \sigma \rangle$ is then a 1-regular subgroup of ${\text{Aut}}(\Lambda )$ (note that $\sigma ^2 = \beta ^{-1}$ fixes the vertex (111) and cyclically permutes its three neighbors in $\Lambda$). Consequently, its natural action on the vertex-set of the dart graph ${\text{D}}(\Lambda )$ is regular, implying that ${\text{D}}(\Lambda )$ is a Cayley graph of $G_1$. Since the group $G_1$ is metacyclic, the graph ${\text{D}}(\Lambda )$ is a tetravalent weak metacirculant (see Sect. 2 for the definition). It is not difficult to see (consider the vertex ([100], (001)) and apply $\sigma$, $\sigma \rho$, $\sigma ^2$ and $\sigma ^2\rho ^3$) that it is in fact isomorphic to ${\mathcal{X}}_{IV}(6,7;3,0;1,0;1,1)$.

We now show that ${\text{D}}(\Lambda )$ admits another regular metacyclic group of automorphisms giving rise to a slightly different presentation of ${\text{D}}(\Lambda )$ as a weak metacirculant. Since $\Lambda$ is not the underlying graph of the cube, the results of [8] imply that ${\text{Aut}}({\text{D}}(\Lambda )) \cong{\text{Aut}}(\Lambda ) \times \langle \tau \rangle$, where $\tau \in{\text{Aut}}({\text{D}}(\Lambda ))$ is the canonical involution exchanging each dart with its reverse. Set $\sigma ' = \tau \beta ^{-1}$. Then $\sigma '$ is of order 6 and

$$\begin{aligned} \sigma '^{-1} \rho \sigma ' = \beta \rho \beta ^{-1} = \rho ^2. \end{aligned}$$

(4)

Observe that $\sigma '$ maps the vertex ((110), [111]) of ${\text{D}}(\Lambda )$ to its neighbor ([111], (011)). The corresponding consistent directed cycle is

$$\begin{aligned} (((110),[111]), ([111],(011)), ((101),[111]), ([111],(110)), ((011),[111]), ([111],(101))), \end{aligned}$$

which is the 6-cycle of ${\text{D}}(\Lambda )$ corresponding to the (white) vertex [111] of $\Lambda$. The $\langle \rho \rangle$-orbit of this 6-cycle thus consists of the seven 6-cycles of ${\text{D}}(\Lambda )$ corresponding to the seven lines of the Fano plane. This shows that the group $G_2 = \langle \rho , \sigma ' \rangle$ is transitive and in fact regular on ${\text{D}}(\Lambda )$. Moreover, the graph ${\text{D}}(\Lambda )$ is isomorphic to ${\mathcal{X}}_{IV}(6,7;2,0;1,0;1,1)$. The corresponding presentation of ${\text{D}}(\Lambda )$ (with labels of some of the vertices) is given in Fig. 4.

Fig. 4

The dart graph of the Heawood graph

We want to point out that (3) and (4) imply that the groups $G_1$ and $G_2$ are not isomorphic. Moreover, the group $G = \langle \rho , \beta , \tau , \pi \rangle = G_1 \langle \tau \rangle = G_1G_2 = \langle \pi \rangle G_2$ acts half-arc-transitively on ${\text{D}}(\Lambda )$ with vertex-stabilizers of order 2. Since the automorphism $\tau \pi \rho ^{-1}$ fixes the vertex ((110), [111]) and interchanges ([111], (011)) with $([110],(110)) = ([111],(011))\rho$, we see that the G-alternating cycles correspond to the induced subgraphs between two “consecutive” $\langle \rho \rangle$-orbits. Therefore, ${\text{rad}}_G({\text{D}}(\Lambda )) = 7 ={\text{att}}_G({\text{D}}(\Lambda ))$ and the graph ${\text{D}}(\Lambda )$ is tightly G-attached. Of course, the full automorphism group ${\text{Aut}}({\text{D}}(\Lambda ))$ acts arc-transitively on ${\text{D}}(\Lambda )$ (with vertex-stabilizers of order 16). In the next subsection we analyze the cyclic covers of ${\text{D}}(\Lambda )$ arising from Constructions 3.1 and 3.4. Before doing so we introduce the following additional terminology. We call the edges of ${\text{D}}(\Lambda )$ of the form $((ijk),[i'j'k'])([i'j'k'],(i''j''k''))$ (the ones “sharing” a common line of the Fano plane) flat and those of the form $([ijk],(i'j'k'))((i'j'k'),[i''j''k''])$ non-flat. Observe that each vertex of ${\text{D}}(\Lambda )$ is incident to two flat and to two non-flat edges and that the 6-cycles consisting of six “consecutive” flat edges correspond to the seven lines of the Fano plane while the 6-cycles consisting of six “consecutive” non-flat edges correspond to the seven points of the Fano plane.

4.2 The Two Families of Covers

Let $m \ge 2$ be an integer. In light of the observations from the previous subsection the two voltage assignments from Constructions 3.1 and 3.4 can be described very easily (where for Construction 3.4 we take $G_1$ as the corresponding 1-regular subgroup of ${\text{Aut}}(\Lambda )$). Observe first that $\rho$ preserves the bipartition of $\Lambda$ and $\rho \in G_1$. Therefore, for each of the two constructions all of the arcs of ${\text{D}}(\Lambda )$ in a given $\langle \rho \rangle$-orbit receive the same voltage. The given voltage assignment is thus completely determined by the voltage assignment on six flat edges (on one from each $\langle \rho \rangle$-orbit) and on six non-flat edges (on one from each $\langle \rho \rangle$-orbit). It can thus be given in a compact way by a diagram on a “doubled 6-cycle” (a multigraph obtained by replacing each edge of a 6-cycle by a pair of parallel edges) where we simply indicate the voltage on each “flat” edge (represented on Fig. 5 as a straight edge) and on each “non-flat” edge. We make the agreement that the edges having no indication of the voltage receive voltage 0.

It is not difficult to verify that the voltage assignment from Construction 3.1 is as given by the diagram from the left-hand side of Fig. 5 (note that the “white” edges from Construction 3.1 are precisely the flat edges) while the voltage assignment from Construction 3.4 is as given by the diagram from the right-hand side of Fig. 5, where we have chosen the orbit $\mathcal{O}$ to be the one containing the directed $G_1$-consistent 6-cycle through ([100], (001), [010]). Here the “top” vertex of the doubled 6-cycle corresponds to the $\langle \rho \rangle$-orbit of the vertex ((110), [111]) and the one following it in the clockwise direction corresponds to the $\langle \rho \rangle$-orbit of the vertex ([111], (011)). The reader will notice that this implies that our covers of ${\text{D}}(\Lambda )$ could actually be described as $({\mathbb{Z}}_7 \times {\mathbb{Z}}_m)$-covers of the doubled 6-cycle. To simplify notation in the rest of this section we make the following agreement. In both constructions the vertices of the ${\mathbb{Z}}_m$-cover of ${\text{D}}(\Lambda )$ are denoted by ordered triples (i, j, k), where $i \in {\mathbb{Z}}_6$, $j \in {\mathbb{Z}}_7$ and $k \in {\mathbb{Z}}_m$, and where (i, j, k) represents the vertex $(((110),[111])\sigma '^i\rho ^j, k)$.

Fig. 5

The diagrams for the two voltage assignments on the dart graph of the Heawood graph

Let us first analyze the covers from Construction 3.1. To this end let $m \ge 1$ and let $\Gamma ^1_m = {\mathcal{C}}_{\text{D}}^{b}(\Lambda , m)$, where we retain the agreement from Sect. 4.1 that the black vertices of $\Lambda$ are the ones corresponding to the points of the Fano plane. By the arguments from Sect. 4.1 the adjacency in $\Gamma ^1_m$ is as follows:

$$\begin{aligned} (i,j,k) \sim (i+1,j,k), (i+1, j+2^i, k + (-1)^{i+1}),\ i \in {\mathbb{Z}}_6,\ j \in {\mathbb{Z}}_7,\ k \in {\mathbb{Z}}_m. \end{aligned}$$

It is thus clear that the permutations $\rho _m$ and $\theta _m$ of the vertex-set of $\Gamma ^1_m$, given by the rules

$$\begin{aligned} (i,j,k)\rho _m&= (i,j-1,k);\ i \in {\mathbb{Z}}_6,\ j \in {\mathbb{Z}}_7,\ k \in {\mathbb{Z}}_m, \end{aligned}$$

(5)

$$\begin{aligned} (i,j,k)\theta _m&= (i,j,k-1);\ i \in {\mathbb{Z}}_6,\ j \in {\mathbb{Z}}_7,\ k \in {\mathbb{Z}}_m, \end{aligned}$$

(6)

are automorphisms of $\Gamma ^1_m$ with $\rho _m$ being (6m, 7)-semiregular, $\theta _m$ being (42, m)-semiregular and $\langle \rho _m, \theta _m \rangle \cong {\mathbb{Z}}_7 \times {\mathbb{Z}}_m$. Let $f :{\mathbb{Z}}_6 \rightarrow {\mathbb{Z}}_7$ be the function defined inductively by setting $f(0) = 3$ and $f(i+1) = f(i) + 2^{i+2}$ for each $i \in {\mathbb{Z}}_6$. It is not difficult to verify that the permutation $\sigma _m$, given by the rule

$$\begin{aligned} (i,j,k)\sigma _m = \left\{ \begin{array}{ccl}(i-1,3j+f(i),k-1) &{} : &{}\quad i{\text{even}},\\ (i-1,3j+f(i),k) &{} : &{}\quad i{\text{odd}},\end{array}\right. \quad \ i \in {\mathbb{Z}}_6,\ j \in {\mathbb{Z}}_7,\ k \in {\mathbb{Z}}_m, \end{aligned}$$

(7)

is an automorphism of $\Gamma ^1_m$. For instance, for each $j \in {\mathbb{Z}}_7$ and $k \in {\mathbb{Z}}_m$ the vertex (0, j, k) is mapped to $(5,3j+3,k-1)$ and its neighbors (1, j, k) and $(1,j+1,k-1)$ are mapped to (0, 3j, k) and $(0,3j+3,k-1)$, respectively, both of which are neighbors of $(5,3j+3,k-1)$. A straightforward computation also shows that

$$\begin{aligned} \sigma _m^{-1}\rho _m\sigma _m = \rho _m^3,\quad \sigma _m\theta _m = \theta _m\sigma _m\quad{\text{and}}\quad \sigma _m^6 = \theta _m^3. \end{aligned}$$

(8)

The group $G_m^1 = \langle \sigma _m, \rho _m, \theta _m \rangle$ is thus clearly regular on $\Gamma _m^1$. This proves half of the following theorem.

Theorem 4.1

Let $\Lambda$ denote the Heawood graph, let $m \ge 1$ be an integer and let $\Gamma = {\mathcal{C}}_{\text{D}}^{b}(\Lambda , m)$. Then $\Gamma$ is a connected arc-transitive tetravalent Cayley graph with vertex-stabilizers of order at least 16. Moreover, writing $m = 3^s m_0$ with $3 \not \mid m_0$ let r, t, q, b be the unique integers with $0 \le r, t, b < 7\cdot 3^s$ and $0 \le q < m_0$ such that all of the following hold:

$$\begin{aligned} 3q&\equiv -1 \pmod{m_0}, \\ r&\equiv 3 \pmod{7} {\text{and}} \ \ r \equiv 1 \pmod{3^s},\\ t&\equiv 0 \pmod{7} \; {\text{and}} \ \ t \equiv 3 \pmod{3^s},\\ b&\equiv 1 \pmod{7 } {\text{and}} \ \ bm_0 \equiv -1 - 3q \pmod{3^s}. \end{aligned}$$

Then $\Gamma \cong {\mathcal{X}}_{IV}(6m_0, 7\cdot 3^s; r, t; 1, 0; 6q+1, b)$. Furthermore, if m is not divisible by 7 then $\Gamma$ admits a half-arc-transitive group of automorphisms relative to which it is tightly-attached with radius 7m.

Proof

By Theorem 3.3 the natural subgroup ${\text{Aut}}(\Lambda ) \times \langle \tau \rangle$ of ${\text{Aut}}({\text{D}}(\Lambda ))$ lifts to ${\text{Aut}}(\Gamma )$, and so $\Gamma$ is an arc-transitive tetravalent graph with vertex-stabilizers of order at least 16. By the above arguments the group $G_m^1 = \langle \sigma _m, \rho _m, \theta _m \rangle$ acts regularly on the vertex-set of $\Gamma$, and so $\Gamma$ is a Cayley graph. Moreover, the lift of the group $G = \langle \rho , \sigma , \tau \rangle$ from Sect. 4.1 acts half-arc-transitively on $\Gamma$ with the G-alternating cycles of ${\text{D}}(\Lambda )$ receiving voltage 7, which clearly shows that when $7 \not \mid m$ the corresponding radius and attachment number are both 7m.

To prove that $\Gamma \cong {\mathcal{X}}_{IV}(6m_0, 7\cdot 3^s; r, t; 1, 0; 6q+1, b)$ observe first that the integers r, t, b and q indeed exist and are uniquely determined by the conditions from the statement of the theorem. Set $\varphi _m = \rho _m \theta _m^{m_0}$. Since $\rho _m$ and $\theta _m$ commute the automorphism $\varphi _m$ is $(6m_0, 7\cdot 3^s)$-semiregular and by definition of r we also have that $\sigma _m^{-1}\varphi _m\sigma _m = \rho _m^3\theta _m^{m_0} = \varphi _m^r$. Thus $\langle \sigma _m, \varphi _m \rangle = G_m^1$ is metacyclic and is transitive on $\Gamma$. By definition of the parameter t we have that $\sigma _m^{6m_0} = \theta _m^{3m_0} = \varphi _m^t$. Note that the two neighbors of the vertex (1, 0, 0) of $\Gamma$ of the form (0, j, k) are $(0,0,0) = (1,0,0)\sigma _m$ and $(0,-1,1)$. By definition of the parameters b and q we have that $(1,0,0)\sigma _m^{6q+1}\varphi _m^b = (0,0,0)\rho _m^b\theta _m^{3q+bm_0} = (0,0,0)\rho _m\theta _m^{-1} = (0,-1,1)$, and so $\Gamma \cong {\mathcal{X}}_{IV}(6m_0, 7\cdot 3^s; r, t; 1, 0; 6q+1, b)$. $\square$

The reader will note that if $3 \not \mid m$ the parameters r, t and b from Theorem 4.1 do not depend on m and one obtains that $\Gamma \cong {\mathcal{X}}_{IV}(6m, 7; 3, 0; 1, 0; 6q+1,1)$. Therefore, in this particular case $\Gamma$ is a very natural generalization of the dart graph of the Heawood graph, namely of ${\mathcal{X}}_{IV}(6, 7; 3, 0; 1, 0; 1, 1)$.

Remark

As we mentioned in the Sect. 1 a mysterious family of arc-transitive graphs emerged when the classification of tetravalent tightly attached half-arc-transitive graphs was obtained in [13, 22]. At that time the authors of [13, 22] did not investigate the origin of this family of graphs, whether there is a natural reason for their arc-transitivity, nor how big their automorphism group really is. Using Theorem 4.1 and the results of [13, 22] it is not difficult to confirm that when $7 \not \mid m$ the graphs ${\mathcal{X}}_{IV}(6m_0, 7\cdot 3^s; r, t; 1, 0; 6q+1, b)$ from Theorem 4.1 all belong to this mysterious family and in fact almost all of the examples from the mysterious family are of this kind (the sole exception is the graph of order 21 which is a ${\mathbb{Z}}_2$-quotient of ${\mathcal{X}}_{IV}(6,7;2,0;1,0;1,1)$). Therefore, the natural reason for their arc-transitivity and their rather large automorphism group is that they arise from the Fano plane and the corresponding Heawood graph.

Remark

Let us also mention the following. Regarding Theorem 4.1 a natural question arises. Is the automorphism group of $\Gamma = {\mathcal{C}}_{\text{D}}^{b}(\Lambda , m)$ equal to the lift of the automorphism group of ${\text{D}}(\Lambda )$ (and so the vertex-stabilizers are of order 16) or does $\Gamma$ admit additional automorphisms which do not project to ${\text{D}}(\Lambda )$? Not to make the paper any longer than it already is we do not pursue this question in detail here. Nevertheless, we strongly believe there are no such additional automorphisms (which can be confirmed at least for the relatively small examples using a computer). A possible approach to proving this conjecture is using the fact that the 6-cycles of ${\text{D}}(\Lambda )$ corresponding to the points and lines of the Fano plane receive voltage 0 and thus lift to 6-cycles. It is not difficult to see that, unless $m = 3$, these are in fact the only 6-cycles of $\Gamma$, so that there is a unique 6-cycle through each edge of $\Gamma$. With a bit more work one should then be able to limit the order of the vertex-stabilizers to $2^4$.

We now turn to the covers of the dart graph ${\text{D}}(\Lambda )$ of the Heawood graph from Construction 3.4. Let $m \ge 1$ be an integer coprime to 3 and let $\Gamma ^2_m = {\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G_1, m)$, where $\Lambda$ is the Heawood graph and $G_1 = \langle \rho , \sigma \rangle$ is the 1-regular subgroup of ${\text{Aut}}(\Lambda )$ from Sect. 4.1. It is easy to verify that the adjacency in $\Gamma ^2_m$ is then as follows (recall our agreement that we identify the vertex-set of $\Gamma ^2_m$ by ${\mathbb{Z}}_6 \times {\mathbb{Z}}_7 \times {\mathbb{Z}}_m$):

$$\begin{aligned} (i,j,k) \sim \left\{ \begin{array}{lcl} (i+1, j, k), (i+1, j+2^i, k+1) &{} : &{}\quad i{\text{even}},\\ (i+1, j, k-1), (i+1, j+2^i, k) &{} : &{}\quad i{\text{odd}},\end{array}\right. \quad i \in {\mathbb{Z}}_6,\ j\in {\mathbb{Z}}_7,\ k \in {\mathbb{Z}}_m . \end{aligned}$$

Similarly as with the covers $\Gamma _m^1$, the permutations $\rho '_m$ and $\theta '_m$ of the vertex-set of $\Gamma ^2_m$, given by the rules

$$\begin{aligned} (i,j,k)\rho '_m&= (i,j+1,k);\ i \in {\mathbb{Z}}_6,\ j \in {\mathbb{Z}}_7,\ k \in {\mathbb{Z}}_m, \end{aligned}$$

(9)

$$\begin{aligned} (i,j,k)\theta '_m&= (i,j,k+1);\ i \in {\mathbb{Z}}_6,\ j \in {\mathbb{Z}}_7,\ k \in {\mathbb{Z}}_m, \end{aligned}$$

(10)

are automorphisms of $\Gamma ^2_m$, generating a group isomorphic to ${\mathbb{Z}}_7 \times {\mathbb{Z}}_m$ with $\rho '_m$ being (6m, 7)-semiregular. It is not difficult to verify that the permutation $\sigma '_m$, given by the rule

$$\begin{aligned} (i,j,k)\sigma '_m = \left\{ \begin{array}{ccl}(i+1,2j,k) &{} : &{}\quad i{\text{even}},\\ (i+1, 2j, k-1) &{} : &{}\quad i{\text{odd}},\end{array}\right. \quad \ i \in {\mathbb{Z}}_6,\ j \in {\mathbb{Z}}_7,\ k \in {\mathbb{Z}}_m, \end{aligned}$$

(11)

is an automorphism of $\Gamma ^2_m$ and that

$$\begin{aligned}{\sigma '_m}^{-1}\rho '_m\sigma '_m ={\rho '_m}^2,\quad \sigma '_m\theta '_m = \theta '_m\sigma '_m\quad{\text{and}}\quad{\sigma '_m}^6 ={\theta '_m}^{-3} \end{aligned}$$

(12)

holds. Since m is coprime to 3 it is clear that the metacyclic group $\langle \sigma '_m, \rho '_m\rangle$ is transitive on $\Gamma ^2_m$ (in fact, it is regular), and so $\Gamma ^2_m$ is a weak metacirculant. Let q be the unique integer with $0< q < m$ such that $3q \equiv -1 \pmod{m}$. Since the vertex (0, 0, 0) is adjacent to both $(1,0,0) = (0,0,0)\sigma '_m$ and $(1,1,1) = (0,0,0){\sigma '_m}^{6q+1}\rho '_m$, this proves some of the claims from the following theorem.

Theorem 4.2

Let $\Lambda$ denote the Heawood graph, let $m > 1$ be an integer coprime to 3 and let $\Gamma = {\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G_1, m)$, where $G_1 \le{\text{Aut}}(\Lambda )$ is as in Sect. 4.1. Then $\Gamma$ is a half-arc-transitive tetravalent Cayley graph with vertex-stabilizers of order 2. Moreover, $\Gamma \cong {\mathcal{X}}_{IV}(6m, 7; 2, 0; 1, 0; 6q + 1, 1)$, where q is the unique integer with $0< q < m$ such that $3q \equiv -1 \pmod{m}$. Furthermore, if m is coprime to 7 the graph $\Gamma$ is tightly attached with radius 7m, while in the case that $7 \mid m$ the radius of $\Gamma$ is m and its attachment number is m/7.

Proof

Since the 1-regular subgroup $G_1$ of ${\text{Aut}}(\Lambda )$ is maximal in ${\text{Aut}}(\Lambda )$ and ${\text{Aut}}(\Lambda )$ is 4-arc-transitive, Theorem 3.6 implies that the subgroup $G_1 \times \langle \tau \rangle$ of ${\text{Aut}}({\text{D}}(\Lambda ))$ is the group of all automorphisms of ${\text{D}}(\Lambda )$ that lift to $\Gamma$. Denote its lift by $\tilde{G}$. In view of the arguments from the paragraph preceding the statement of Theorem 4.2 we thus only need to verify that ${\text{Aut}}(\Gamma ) = \tilde{G}$ and to prove the claims regarding the radius and the attachment number of $\Gamma$.

Of the two paired $\tilde{G}$-induced orientations of the edges of $\Gamma$ choose the one in which the edge (0, 0, 0)(1, 0, 0) is oriented from (0, 0, 0) to (1, 0, 0). The nature of the action of $\tilde{G}$ (which is clearly generated by $\sigma '_m, \rho '_m$ from (11) and (9) and the lift of $\tau \pi$ from Sect. 4.1) then implies that each edge of the form $(i,j,k)(i+1,j',k')$ is oriented from (i, j, k) to $(i+1,j',k')$. Let K be the subgroup of ${\text{Aut}}(\Gamma )$ of all automorphisms preserving this orientation of the edges of $\Gamma$. Of course, $\tilde{G} \le K$ and K acts half-arc-transitively on $\Gamma$.

It is not difficult to verify that for each edge of ${\text{D}}(\Lambda )$ precisely eleven 6-cycles pass through it (one corresponds to the corresponding point or line of the Fano plane, six of them are 6-cycles obtained by joining two “halves” of 6-cycles corresponding to points and lines of the Fano plane, while the remaining four correspond to 6-cycles of $\Lambda$ through the corresponding 2-arc of $\Lambda$). Moreover, of these eleven 6-cycles precisely four receive the trivial voltage (and thus lift to 6-cycles of $\Gamma$), while the remaining ones receive voltages $\pm 1$ and $\pm 3$ (and thus do not lift to 6-cycles of $\Gamma$). More precisely, consider for instance the edge $e = ((110),[111])([111],(011))$ of ${\text{D}}(\Lambda )$. There are two trivial voltage 6-cycles through e that also contain ((101), [111]) - one of them obtained by joining the 6-cycles corresponding to the line [111] and the point (101) of the Fano plane, and the other by joining the 6-cycles corresponding to the line [111] and the point (110). There are two trivial voltage 6-cycles through e that also contain ((011), [011])—one of them obtained by joining the 6-cycles corresponding to the line [111] and the point (011) of the Fano plane, and the other corresponding to the 6-cycle ((110), [111], (011), [011], (100), [001]) of $\Lambda$. However, there is no trivial voltage 6-cycle through e that also contains ((011), [100]). This shows that there is no 6-cycle of $\Gamma$ containing the $\tilde{G}$-alternating path $((0,0,0),(1,0,0),(0,-1,-1))$ while for each of the $\tilde{G}$-directed paths $((0,0,0),(1,0,0),(2,0,-1))$ and ((0, 0, 0), (1, 0, 0), (2, 2, 0)) there are two 6-cycles of $\Gamma$ containing it. Observe that this implies that the sets $V_i = \{(i,j,k) :j \in {\mathbb{Z}}_7, k\in {\mathbb{Z}}_m\}$, $i \in {\mathbb{Z}}_6$, are blocks of imprimitivity for the action of the full automorphism group ${\text{Aut}}(\Gamma )$, proving that $[{\text{Aut}}(\Gamma ) : K] \le 2$.

Recall that for the half-arc-transitive action of $G_1 \langle \tau \rangle$ on ${\text{D}}(\Lambda )$ the corresponding radius and attachment number are 7 and observe that the corresponding alternating cycles receive voltage 7. Therefore, if m is coprime to 7 the $\tilde{G}$-radius of $\Gamma$ is 7m, and so $\Gamma$ is $\tilde{G}$-tightly attached. Suppose now that $7 \mid m$. Then the $\tilde{G}$-radius of $\Gamma$ is m. It is easy to see that the set of the vertices of the form (1, j, k) that are contained on the $\tilde{G}$-alternating cycle containing (1, 0, 0) and (0, 0, 0) is $\{(1,k,k) :0 \le k < m\}$. Similarly, the set of the vertices of the form (1, j, k) that are contained on the $\tilde{G}$-alternating cycle containing (1, 0, 0) and (2, 2, 0) is $\{(1,2k,k) :0 \le k < m\}$. As $7 \mid m$ the intersection of these two sets is $\{(1,0,7k) :0 \le k < m/7\}$, and so the $\tilde{G}$-attachment number is m/7.

We now finally prove that ${\text{Aut}}(\Gamma ) = \tilde{G}$. Using a computer one easily verifies that this is indeed the case for $m = 2$ (in which case $\Gamma \cong {\mathcal{X}}_{IV}(12, 7; 2, 0; 1, 0; 7, 1)$), for $m = 7$ (in which case $\Gamma \cong {\mathcal{X}}_{IV}(42, 7; 2, 0; 1, 0; 13, 1)$) and for $m = 14$ (in which case $\Gamma \cong {\mathcal{X}}_{IV}(84, 7; 2, 0; 1, 0; 55, 1)$). For the rest of the proof we thus assume that either $m > 2$ is coprime to 7 or $m > 14$. The above argument shows that in this case the $\tilde{G}$-attachment number of $\Gamma$ is at least 3, and so [14, Lemma 3.5] implies that the vertex-stabilizers of the action of K on $\Gamma$ are of order 2. This shows that $K = \tilde{G}$ and consequently $[{\text{Aut}}(\Gamma ):\tilde{G}] \le 2$. By way of contradiction suppose that $\tilde{G}$ is an index 2 subgroup of ${\text{Aut}}(\Gamma )$. Then $\tilde{G}$ is normal in ${\text{Aut}}(\Gamma )$ and there exists a unique $\alpha \in{\text{Aut}}(\Gamma ) \setminus \tilde{G}$ fixing (1, 0, 0) and mapping $(2,0,-1)$ to (0, 0, 0). Since $\tilde{G} = K$ is normal in ${\text{Aut}}(\Gamma )$ and $\alpha \notin \tilde{G}$ it follows that $\alpha$ reverses the orientation of each edge, and so it maps $\tilde{G}$-alternating cycles to $\tilde{G}$-alternating cycles. Consider now the walk obtained by starting with the 2-path ((0, 0, 0), (1, 0, 0), (2, 2, 0)) and then extending it 13 times in such a way that at each step we add one vertex at each of the two endvertices of the current path in a $\tilde{G}$-alternating way. For instance, at the first step we obtain the walk ((1, 1, 1), (0, 0, 0), (1, 0, 0), (2, 2, 0), (1, 2, 1)) and we obtain the walk ((0, 1, 1), (1, 1, 1), (0, 0, 0), (1, 0, 0), (2, 2, 0), (1, 2, 1), (2, 4, 1)) at the second step. The obtained walk is closed with (1, 0, 7) being antipodal to (1, 0, 0) (and it can be verified that, as $m \notin \{2,3\}$, it is in fact a cycle). If however we do the same starting with the walk $((0,0,0),(1,0,0),(2,0,-1))$ then the endvertices of the obtained walk are (1, 0, 7) and $(1,0,-7)$, which are different as $m \notin \{2,7,14\}$. Letting the flat edges of $\Gamma$ be the ones covering the flat edges of ${\text{D}}(\Lambda )$ (see the end of Sect. 4.1) and taking into account that ${\text{Aut}}(\Gamma )$ preserves the set of $\tilde{G}$-alternating cycles and thus also the set of $\tilde{G}$-alternating 2-paths, we thus find that the 2-path ((0, 0, 0), (1, 0, 0), (2, 2, 0)), which consists of a flat and a non-flat edge, is essentially different from the 2-path $((0,0,0),(1,0,0),(2,0,-1))$, which consists of two flat edges. Since $\alpha$ fixes (1, 0, 0) and maps the flat edge $(1,0,0)(2,0,-1)$ to the flat edge (0, 0, 0)(1, 0, 0) it thus follows that it has to preserve the set of flat edges (and consequently also the set of non-flat edges) of $\Gamma$.

Finally, observe that starting at a vertex (i, j, k) and then traversing six consecutive flat edges (in one of the two possible directions from (i, j, k)) we arrive at $(i,j,k+3)$ or $(i,j,k-3)$, which are both in the same ${\mathbb{Z}}_m$-fibre. Since m is coprime to 3 and $\alpha$ preserves the set of flat edges of $\Gamma$ it also preserves the set of ${\mathbb{Z}}_m$-fibres. But then $\alpha$ has to be a lift of some automorphism from ${\text{Aut}}({\text{D}}(\Lambda ))$, that is $\alpha \in \tilde{G}$, a contradiction. This finally proves that $\tilde{G} ={\text{Aut}}(\Gamma )$, as claimed. $\square$

Remark

Recall that the dart graph of the Heawood graph is isomorphic to ${\mathcal{X}}_{IV}(6,7;3,0;1,0;1,1)$ as well as to ${\mathcal{X}}_{IV}(6,7;2,0;1,0;1,1)$. Somewhat surprisingly, Theorems 4.1 and 4.2 imply that for each $m > 1$, coprime to 3, the graphs ${\mathcal{X}}_{IV}(6m, 7; 3, 0; 1, 0; 6q+1, 1)$ and ${\mathcal{X}}_{IV}(6m, 7; 2, 0; 1, 0; 6q+1, 1)$, where q is the unique integer with $0< q < m$ and $3q \equiv -1 \pmod{m}$, are not isomorphic. In fact, the first one is arc-transitive with vertex-stabilizers of order at least 16, while the second one is half-arc-transitive with vertex-stabilizers of order 2.

Remark

Let $\Lambda$ be the Heawood graph and let $m > 1$ be an integer coprime to 21. Since the half-arc-transitive graph ${\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G_1, m)$ from Theorem 4.2 is tightly-attached with radius 7m, the classification of tetravalent tightly attached half-arc-transitive graphs from [13, 22] implies that it has to be isomorphic to a graph of the form ${\mathcal{X}}_o(6,7m;\tilde{r})$ or ${\mathcal{X}}_e(6,7m;\tilde{r},\tilde{t})$ from [22], depending on whether m is odd or even, respectively. Moreover, the results of [21] imply that the parameter $\tilde{r}$ corresponds to the so-called alternating jump parameter of the graph in question (see [21] for the definition and the corresponding result). It is thus not difficult to see that $\tilde{r}$ can be taken as the unique integer with $0 \le \tilde{r} < 7m$ such that $\tilde{r} \equiv 2 \pmod{7}$ and $\tilde{r} \equiv 1 \pmod{m}$. For instance, for the graph ${\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G_1, 2)$, which by Theorem 4.2 is isomorphic to ${\mathcal{X}}_{IV}(12,7;2,0;1,0;7,1)$, we get $\tilde{r} = 9$, and so the results of [22] imply that $\tilde{t} = 7$, that is ${\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G_1, 2) \cong {\mathcal{X}}_{IV}(12,7;2,0;1,0;7,1) \cong {\mathcal{X}}_e(6,14;9,7) \cong {\mathcal{X}}_e(6,14;3,0)$ (see [22, Proposition 9.1]). Similarly, for the graph ${\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G_1, 5) \cong {\mathcal{X}}_{IV}(30,7;2,0;1,0;19,1)$ we get $\tilde{r} = 16$, and so ${\mathcal{C}}_{\text{D}}^{b,1}(\Lambda , G_1, 5) \cong {\mathcal{X}}_{IV}(30,7;2,0;1,0;19,1) \cong {\mathcal{X}}_o(6,35;16) \cong {\mathcal{X}}_o(6,35;11)$ (see [13, Proposition 4.1]).