# Edge-transitive core-free Nest graphs

István Kovács  I. Kovács
UP IAM, University of Primorska, Muzejski trg 2, SI-6000 Koper, Slovenia
UP FAMNIT, University of Primorska, Glagolǰaska ulica 8, SI-6000 Koper,
Slovenia<EMAIL_ADDRESS>
###### Abstract.

A finite simple graph $\Gamma$ is called a Nest graph if it is regular of
valency $6$ and admits an automorphism $\rho$ with two orbits of the same
length such that at least one of the subgraphs induced by these orbits is a
cycle. We say that $\Gamma$ is core-free if no non-trivial subgroup of the
group generated by $\rho$ is normal in $\operatorname{Aut}(\Gamma)$. In this
paper we show that, if $\Gamma$ is edge-transitive and core-free, then it is
isomorphic to one of the following graphs: the complement of the Petersen
graph, the Hamming graph $H(2,4)$, the Shrikhande graph and a certain normal
$2$-cover of $K_{3,3}$ by $\mathbb{Z}_{2}^{4}$.

###### Key words and phrases:

bicriculant, edge-transitive, primitive permutation group

###### 2010 Mathematics Subject Classification:

05C25, 20B25

Partially supported by the Slovenian Research Agency (research program
P1-0285, research projects N1-0062, J1-9108, J1-1695, J1-2451, N1-0140 and
N1-0208).

##  1\. Introduction

All groups in this paper will be finite and all graphs will be finite and
simple. A graph admitting an automorphism with two orbits of the same length
is called a bicirculant. Symmetry properties of bicirculants have attracted
considerable attention (see, e.g., [1, 5, 7, 16, 22, 23, 25, 29]). Following
[17], for an integer $d\geq 3$, we denote by $\mathcal{F}(d)$ the family of
regular graphs having valency $d$ and admitting an automorphism with two
orbits of the same length such that at least one of the subgraphs induces by
these orbits is a cycle. Jajcay et al. [11] initiated the investigation of the
edge-transitive graphs in the classes $\mathcal{F}(d)$, $d\geq 6$. The
families $\mathcal{F}(d)$ with $3\leq d\leq 5$ were studied under different
names. The graphs in $\mathcal{F}(3)$ were introduced by Watkins [27] under
the name generalised Petersen graphs, the graphs in $\mathcal{F}(4)$ by Wilson
[28] under the name Rose Window graphs, and the graphs in $\mathcal{F}(5)$ by
Arroyo et al. [2] under the name Tabačjn graphs. The automorphism groups of
these graphs form the subject of the papers [10, 15, 9, 18], and the question
which of them are edge-transitive has been answered in [10, 15, 2].

Jajcay et al. [11] asked whether there exist edge-transitive graphs in
$\mathcal{F}(d)$ for $d\geq 6$. Following [26], they call the graphs in
$\mathcal{F}(6)$ Nest graphs. Several infinite families of edge-transitive
Nest graphs were exhibited, which turn out to have interesting properties
(e.g., half-arc-transitivity). However, no edge-transitive graph of valency
larger than $6$ was found. Recently, it was proved by the author and Ruff [17]
that the complement of the Petersen graph is the only edge-transitive graph in
$\mathcal{F}(d)$ with $d\geq 6$, which has twice an odd number of vertices.
The main result of [11] is the classification of the edge-transitive Nest
graphs of girth $3$ (see [11, Theorem 8]), and the task to classify all edge-
transitive Nest graphs was posed as [11, Problem 2]. In what follows, the Nest
graphs will be described via their representation due to [11, Construction 3],
which goes as follows. Let $n\geq 4$ and let $a,b,c,k\in\mathbb{Z}_{n}$ such
that each of them is distinct from $0$ (the zero element of $\mathbb{Z}_{n}$),
the elements $a,b$ and $c$ are pairwise distinct, and in the case when $n$ is
even, $k\neq n/2$. Then the Nest graph $\operatorname{\mathcal{N}}(n;a,b,c;k)$
is defined to have vertex set
$\\{u_{i}:i\in\mathbb{Z}_{n}\\}\cup\\{v_{i}:i\in\mathbb{Z}_{n}\\}$, and three
types of edges such as

  * •

$\\{u_{i},u_{i+1}\\}$ for $i\in\mathbb{Z}_{n}$ (rim edges),

  * •

$\\{v_{i},v_{i+k}\\}$ for $i\in\mathbb{Z}_{n}$ (hub edges),

  * •

$\\{u_{i},v_{i}\\}$, $\\{u_{i},v_{i+a}\\}$, $\\{u_{i},v_{i+b}\\}$ and
$\\{u_{i},v_{i+c}\\}$ for $i\in\mathbb{Z}_{n}$ (spoke edges),

where the sums in the subscripts are computed in $\mathbb{Z}_{n}$. It is easy
to see that the permutation $\rho$ of $V(\Gamma)$, defined as
$\rho=(u_{0},u_{1},\ldots,u_{n-1})(v_{0},v_{1},\ldots,v_{n-1})$, is an
automorphism of $\Gamma$ with orbits $\\{u_{i}:i\in\mathbb{Z}_{n}\\}$ and
$\\{v_{i}:i\in\mathbb{Z}_{n}\\}$, and the subgraph induced by the former orbit
is a cycle. It is not hard to show that all the graphs
$\operatorname{\mathcal{N}}(n;a,b,c;k)$ comprise the whole family
$\mathcal{F}(6)$.

In the case of both the Rose Window and the Tabačjn graphs, the classification
of the edge-transitive graphs was obtained in two main steps. The so called
core-free graphs were found first and the rest was retrieved from the core-
free graphs using covering techniques (see [15, 2]). Here is the formal
definition of a core-free Nest graph.

######  Definition 1.1.

Let $\Gamma=\operatorname{\mathcal{N}}(n;a,b,c;k)$ be a Nest graph and $\rho$
be the permutation of $V(\Gamma)$ defined as
$\rho=(u_{0},u_{1},\ldots,u_{n-1})(v_{0},v_{1},\ldots,v_{n-1})$. Then $\Gamma$
is core-free if no non-trivial subgroup of $\langle\rho\rangle$ (the group
generated by $\rho$) is normal in $\operatorname{Aut}(\Gamma)$.

######  Remark.

The term “core-free” comes from group theory. For a subgroup $A\leq B$, the
core of $A$ in $B$ is the largest normal subgroup of $B$ contained in $A$. In
the case when $A$ has trivial core, it is also called core-free. In this
context, Definition 1.1 can be rephrased by saying that $\Gamma$ is core-free
if and only if $\langle\rho\rangle$ is core-free in
$\operatorname{Aut}(\Gamma)$.

Our goal in this paper is to determine the edge-transitive core-free Nest
graphs. For an explanation why this task is a more subtle than in the case of
Rose Window and Tabačjn graphs, we refer to [11, p. 9]. The edge-transitive
non-core-free Nest graphs are handled in the paper [14].

The main result of this paper is the following theorem.

######  Theorem 1.2.

If $\operatorname{\mathcal{N}}(n;a,b,c;k)$ is an edge-transitive core-free
graph, then it is isomorphic to one of the following graphs:

$\operatorname{\mathcal{N}}(5;1,2,3;2),~{}\operatorname{\mathcal{N}}(8;1,3,4;3),~{}\operatorname{\mathcal{N}}(8;1,2,5;3)~{}\text{and}~{}\operatorname{\mathcal{N}}(12;2,4,8;5).$

######  Remark.

The fact that each of the Nest graphs in Theorem 1.2 is core-free was
mentioned by Jajcay et al., see [11, p. 9]. The first three of them are well-
known strongly regular graphs. The Nest graph
$\operatorname{\mathcal{N}}(5;1,2,3;2)$ is the complement of the Petersen
graph, $\operatorname{\mathcal{N}}(8;1,3,4;3)$ is the Hamming graph $H(2,4)$,
and $\operatorname{\mathcal{N}}(8;1,2,5;3)$ is the Shrikhande graph. The
fourth Nest graph $\operatorname{\mathcal{N}}(12;2,4,8;5)$ is not strongly-
regular, it can be described as a normal $2$-cover of the complete bipartite
graph $K_{3,3}$ by $\mathbb{Z}_{2}^{4}$ (for the definition of a normal
$2$-cover, see the 2nd paragraph of Subsection 2.1).

The paper is organised as follows. Section 2 contains the needed results from
graph and group theory. In Section 3 we review some results about Nest graphs
obtained in [11, 17]. Section 4 is devoted to the Nest graphs in the form
$\operatorname{\mathcal{N}}(2m;2,m,2+m;1)$, $m$ is odd. The main result
(Proposition 4.1) is a characterisation, which was mentioned in [11] without a
proof, and which is needed for us in the proof Theorem 1.2. The latter proof
is presented in Section 5.

##  2\. Preliminaries

###  2.1. Graph theory

Given a graph $\Gamma$, let $V(\Gamma)$, $E(\Gamma)$, $A(\Gamma)$ and
$\operatorname{Aut}(\Gamma)$ denote its vertex set, edge set, arc set and
automorphism group, respectively. The number $|V(\Gamma)|$ is called the order
of $\Gamma$. The set of vertices adjacent with a given vertex $v$ is denoted
by $\Gamma(v)$. If $G\leq\operatorname{Aut}(\Gamma)$ and $v\in V(\Gamma)$,
then the stabiliser of $v$ in $G$ is denoted by $G_{v}$, the orbit of $v$
under $G$ by $v^{G}$, and the set of all $G$-orbits by
$\operatorname{Orb}(G,V(\Gamma))$. If $B\subseteq V(\Gamma)$, then the setwise
stabiliser of $B$ in $G$ is denoted by $G_{\\{B\\}}$. If $G$ is transitive on
$V(\Gamma)$, then $\Gamma$ is said to be $G$-vertex-transitive, and $\Gamma$
is simply called vertex-transitive when it is
$\operatorname{Aut}(\Gamma)$-vertex-transitive; ($G$-)edge- and ($G$-)arc-
transitive graphs are defined correspondingly.

Let $\pi$ be an arbitrary partition of $V(\Gamma)$ and for a vertex $v\in
V(\Gamma)$, let $\pi(v)$ denote the class containing $v$. The quotient graph
of $\Gamma$ with respect to $\pi$, denoted by $\Gamma/\pi$, is defined to have
vertex set $\pi$, and edges $\\{\pi(u),\pi(v)\\}$, where $\\{u,v\\}\in
E(\Gamma)$ such that $\pi(u)\neq\pi(v)$. Now, if there exists a constant $r$
such that

$\forall\\{u,v\\}\in
E(\Gamma):~{}\pi(u)\neq\pi(v)~{}\text{and}~{}|\Gamma(u)\cap\pi(v)|=r,$

then $\Gamma$ is called an $r$-cover of $\Gamma/\pi$. The term cover will also
be used instead of $1$-cover. In the special case when
$\pi=\operatorname{Orb}(N,V(\Gamma))$ for an intransitive normal subgroup
$N\lhd\operatorname{Aut}(\Gamma)$, $\Gamma/N$ will also be written for
$\Gamma/\pi$ and when $\Gamma$ is also an $r$-cover (cover, respectively) of
$\Gamma/N$, then the term normal $r$-cover (normal cover, respectively) will
also be used. It is well-known that this is always the case when $\Gamma$ is
edge-transitive. More precisely, if $\Gamma$ is a $G$-edge-transitive graph,
$\Gamma$ is regular with valency $\kappa$, and $N\lhd G$ is intransitive, then
$\Gamma$ is a normal $r$-cover of $\Gamma/N$ for some $r$ and $r$ divides
$\kappa$.

A graph admitting a regular cyclic group of automorphisms is called circulant.
A recursive classification of finite arc-transitive circulants was obtained
independently by Kovács [13] and Li [19]. The paper [13] also provides an
explicit characterisation (see [13, Theorem 4]), which was rediscovered
recently by Li et al. [20]. The characterisation presented below follows from
the proof of [13, Theorem 4] or from [20, Theorem 1.1].

In what follows, given a cyclic group $C$ and a divisor $d$ of $|C|$, we
denote by $C_{d}$ the unique subgroup of $C$ of order $d$.

######  Theorem 2.1.

([13]) Let $\Gamma$ be a connected arc-transitive graph of order $n$ and of
valency $\kappa$ and suppose that $C\leq\operatorname{Aut}(\Gamma)$ is a
regular cyclic subgroup. Then one of the following holds.

  1. (a)

$\Gamma$ is the complete graph.

  2. (b)

$C$ is normal in $\operatorname{Aut}(\Gamma)$.

  3. (c)

$\mathcal{B}=\operatorname{Orb}(C_{d},V(\Gamma))$ is a block system for
$\operatorname{Aut}(\Gamma)$ for some divisor $d$ of $\gcd(n,\kappa)$, $d>1$.
$\Gamma$ is a normal $d$-cover of $\Gamma/\mathcal{B}$, and
$\Gamma/\mathcal{B}$ is a connected arc-transitive circulant of valence
$\kappa/d$.

  4. (d)

$\mathcal{B}_{1}=\operatorname{Orb}(C_{d},V(\Gamma))$ and
$\mathcal{B}_{2}=\operatorname{Orb}(C_{n/d},V(\Gamma))$ are block systems for
$\operatorname{Aut}(\Gamma)$ for some divisor $d$ of $n$ such that $d>3$,
$\gcd(d,n/d)=1$ and $d-1$ divides $\kappa$. $\Gamma/\mathcal{B}_{1}$ is a
connected arc-transitive circulant of valency $\kappa/(d-1)$,
$\Gamma/\mathcal{B}_{2}\cong K_{d}$, and

$\operatorname{Aut}(\Gamma)=G_{1}\times G_{2},$ (1)

where $C_{d}\leq G_{1}$, $G_{1}\cong S_{d}$, $C_{n/d}<G_{2}$, and
$G_{2}\cong\operatorname{Aut}(\Gamma/\mathcal{B}_{1})$.

######  Remark.

Although not used later, it is worth mentioning that the graph $\Gamma$ in
part (c) is isomorphic to the lexicographical product
$\Gamma/\mathcal{B}[\overline{K}_{d}]$, where $\overline{K}_{d}$ is the
edgeless graph on $d$ vertices, and the graph $\Gamma$ in part (d) is
isomorphic to the tensor (direct) product $K_{d}\times\Gamma/\mathcal{B}_{1}$
(see [13, 20]).

In the rest of the section we restrict ourselves to arc-transitive circulants
of small valency.

######  Lemma 2.2.

([3, part (ii) of Corollary 1.3]) Let $\Gamma$ be a connected arc-transitive
graph of order $n$ and of valency $\kappa$, where $\kappa=3$ or $4$, and
suppose that $C\leq\operatorname{Aut}(\Gamma)$ is a regular cyclic subgroup.
Then one of the following holds.

  1. (1)

$\Gamma$ is isomorphic to one of the graphs: $K_{4},K_{5},K_{3,3}$ and
$K_{5,5}-5K_{2}$.

  2. (2)

$\kappa=4$ and $C$ is normal in $\operatorname{Aut}(\Gamma)$.

  3. (3)

$\kappa=4$, $n$ is even, $\mathcal{B}=\operatorname{Orb}(C_{2},V(\Gamma))$ is
a block system for $\operatorname{Aut}(\Gamma)$, and $\Gamma$ is a normal
$2$-cover of $\Gamma/\mathcal{B}$, which is a cycle.

######  Lemma 2.3.

Let $\Gamma$ be a connected arc-transitive graph of order $n>14$ and of
valency $6$, and suppose that $C\leq\operatorname{Aut}(\Gamma)$ is a regular
cyclic subgroup. Then $\operatorname{Aut}(\Gamma)$ contains a normal subgroup
$N$ such that one of the following holds.

  1. (1)

$N=C$, or

  2. (2)

$n\equiv 4\\!\\!\pmod{8}$ and $N=C_{n/4}$, or

  3. (3)

$N\cong\mathbb{Z}_{3}^{\ell}$ for $\ell\geq 2$ and $C_{3}<N$.

###### Proof.

$\Gamma$ belongs to one of the families (a)–(d) in Theorem 2.1.

Family (a): This case cannot occur as $n>14$.

Family (b): Part (1) follows.

Family (c): In this case $\operatorname{Orb}(C_{d},V(\Gamma))$ is a block
system for $\operatorname{Aut}(\Gamma)$, where $d=2$ or $d=3$. Let
$\mathcal{B}=\operatorname{Orb}(C_{d},V(\Gamma))$.

If $d=2$, then $\Gamma/\mathcal{B}$ has valency $3$. It follows from Lemma 2.2
that $n\leq 12$, but this is excluded.

If $d=3$, then choose $N$ to be the Sylow $3$-subgroup of the kernel of the
action of $\operatorname{Aut}(\Gamma)$ on $\mathcal{B}$. It follows that
$N\cong\mathbb{Z}_{3}^{\ell}$ for some $\ell\geq 2$. Also, $N$ is
characteristic in the latter kernel, which implies that
$N\lhd\operatorname{Aut}(\Gamma)$. Finally,
$\operatorname{Orb}(N,V(\Gamma))=\mathcal{B}=\operatorname{Orb}(C_{3},V(\Gamma))$,
and so $C_{3}<N$, i.e., part (3) holds.

Family (d): In this case it follows from the assumption that $n>14$ that
$\operatorname{Orb}(C_{4},V(\Gamma))$ and
$\operatorname{Orb}(C_{n/4},V(\Gamma))$ are block systems for
$\operatorname{Aut}(\Gamma)$ and $n\equiv 4\\!\\!\pmod{8}$. Furthermore,

$\operatorname{Aut}(\Gamma)=G_{1}\times G_{2},$

where $C_{4}<G_{1}$, $G_{1}\cong S_{4}$, $C_{n/4}<G_{2}$ and
$G_{2}\cong\operatorname{Aut}(\Gamma/\mathcal{B}_{1})$, where
$\mathcal{B}_{1}=\operatorname{Orb}(C_{4},V(\Gamma))$. The graph
$\Gamma/\mathcal{B}_{1}$ is connected of valency $2$, hence it is a cycle of
length $n/4$. It follows that $C_{n/4}$ is characteristic in $G_{2}$, and as
$G_{2}\lhd\operatorname{Aut}(\Gamma)$, part (2) follows. ∎

###  2.2. Group theory

Our terminology and notation are standard and we follow the books [8, 12]. The
socle of a group $G$, denoted by $\operatorname{soc}(G)$, is the subgroup
generated by the set of all minimal normal subgroups (see [8, p. 111]). The
group $G$ is called almost simple if $\operatorname{soc}(G)=T$, where $T$ is a
non-abelian simple group. In this case $G$ is embedded in
$\operatorname{Aut}(T)$ so that its socle is embedded via the inner
automorphisms of $T$, and we also write $T\leq G\leq\operatorname{Aut}(T)$
(see [8, p. 126]).

Our proof of Theorem 1.2 relies on the classification of primitive groups
containing a cyclic subgroup with two orbits due to Müller [24]. Here we need
only the special case when the cyclic subgroup is semiregular.

######  Theorem 2.4.

([24, Theorem 3.3]) Let $G$ be a primitive permutation group of degree $2n$
containing an element with two orbits of the same length. Then one of the
following holds, where $G_{0}$ denotes the stabiliser of a point in $G$.

  1. (1)

(Affine action) $\mathbb{Z}_{2}^{m}\lhd G\leq\operatorname{AGL}(m,2)$, where
$n=2^{m-1}$. Furthermore, one of the following holds.

    1. (a)

$n=2$, and $G_{0}=\operatorname{GL}(2,2)$.

    2. (b)

$n=2$, and $G_{0}=\operatorname{GL}(1,4)$.

    3. (c)

$n=4$, and $G_{0}=\operatorname{GL}(3,2)$.

    4. (d)

$n=8$, and $G_{0}$ is one of the following groups:
$\mathbb{Z}_{5}\rtimes\mathbb{Z}_{4}$, $\operatorname{\Gamma L}(1,16)$,
$(\mathbb{Z}_{3}\times\mathbb{Z}_{3})\rtimes\mathbb{Z}_{4}$,
$\operatorname{\Sigma L}(2,4)$, $\operatorname{\Gamma L}(2,4)$, $A_{6}$,
$\operatorname{GL}(4,2)$, $(S_{3}\times S_{3})\rtimes\mathbb{Z}_{2}$, $S_{5}$,
$S_{6}$ and $A_{7}$.

  2. (2)

(Almost simple action) $G$ is an almost simple group and one of the following
holds.

    1. (a)

$n\geq 3$, $\operatorname{soc}(G)=A_{2n}$, and $A_{2n}\leq G\leq S_{2n}$ in
its natural action.

    2. (b)

$n=5$, $\operatorname{soc}(G)=A_{5}$, and $A_{5}\leq G\leq S_{5}$ in its
action on the set of $2$-subsets of $\\{1,2,3,4,5\\}$.

    3. (c)

$n=(q^{d}-1)/2(q-1)$, $\operatorname{soc}(G)=\operatorname{PSL}(d,q)$, and
$\operatorname{PSL}(d,q)\leq G\leq\operatorname{P\Gamma L}(d,q)$ for some odd
prime power $q$ and even number $d\geq 2$ such that $(d,q)\neq(2,3)$.

    4. (d)

$n=6$ and $\operatorname{soc}(G)=G=M_{12}$.

    5. (e)

$n=11$, $\operatorname{soc}(G)=M_{22}$, and $M_{22}\leq
G\leq\operatorname{Aut}(M_{22})$.

    6. (f)

$n=12$ and $\operatorname{soc}(G)=G=M_{24}$.

If $G$ is a group in one of the families (a)-(f) in part (2) above, then it
follows from [8, Theorem 4.3B] that $\operatorname{soc}(G)$ is the unique
minimal normal subgroup of $G$. Therefore, we have the following corollary.

######  Corollary 2.5.

Let $G$ be a primitive permutation group in one of the families (a)-(f) in
part (2) of Theorem 2.4, and let $N\lhd G$, $N\neq 1$. Then $N$ is also
primitive.

For a transitive permutation group $G\leq\operatorname{Sym}(\Omega)$, the
subdegrees of $G$ are the lengths of the orbits of a point stabiliser
$G_{\omega}$, $\omega\in\Omega$. Since $G$ is transitive, it follows that the
subdegrees do not depend on the choice of $\omega$ (see [8, p. 72]). The
number of orbits of $G_{\omega}$ is called the rank of $G$. The actions of a
group $G$ on sets $\Omega$ and $\Omega^{\prime}$ are said to be equivalent if
there is a bijection $\varphi:\Omega\to\Omega^{\prime}$ such that

$\forall\omega\in\Omega,~{}\forall g\in
G:~{}\varphi(\omega^{g})=(\varphi(\omega))^{g}.$

Now, suppose that $G$ is a group in one of the families (a)-(f) in part (2) of
Theorem 2.4. If $G$ is in family (a), then the action is unique up to
equivalence and $G$ is clearly $2$-transitive. If $G$ is in family (b), then
the action is unique up to equivalence and the subdegrees are $1,3$ and $6$.
Let $G$ be in family (c). The semiregular cyclic subgroup of $G$ with two
orbits is contained in a regular cyclic group, called the Singer subgroup of
$\operatorname{PGL}(d,q)$ (see [12, Chapter 2, Theorem 7.3]). In this case the
action is unique up to equivalence if and only if $d=2$. If $d\geq 4$, then
the action of $G$ is equivalent to either its natural action on the set of
points of the projective geometry $\operatorname{PG}(d-1,q)$, or to its
natural action on the set of hyperplanes of $\operatorname{PG}(d-1,q)$. In
both actions $G$ is $2$-transitive. Finally, if $G$ is in the families
(d)-(f), then the action is unique up to equivalence and $G$ is $2$-transitive
(this can also be read off from [6]). All this information is summarised in
the lemma below.

######  Lemma 2.6.

Let $G$ be a primitive permutation group in one of the families (a)-(f) in
part (2) of Theorem 2.4.

  1. (1)

$G$ is $2$-transitive, unless $G$ belongs to family (b). In the latter case
the subdegrees are $1,3$ and $6$.

  2. (2)

The action of $G$ is unique up to equivalence, unless $G$ is in family (c) and
$d\geq 4$. In the latter case $G$ admits two inequivalent faithful actions,
namely, the natural actions on the set of points and the set of hyperplanes,
respectively, of the projective geometry $\operatorname{PG}(d-1,q)$.

The following result about $G$-arc-transitive bicirculants can be found in
Devillers et al. [7]. The proof works also for the edge-transitive
bicirculants, in fact, it is an easy consequence of Theorem 2.4.

######  Proposition 2.7.

([7, part (1) of Proposition 4.2]) Let $\Gamma$ be a $G$-edge-transitive
bicirculant such that $G$ is a primitive group. Then $\Gamma$ is one of the
following graphs:

  1. (1)

The complete graph, and $G$ is one of the $2$-transitive groups described in
part (2) of Theorem 2.4.

  2. (2)

The Petersen graph or its complement, and $A_{5}\leq G\leq S_{5}$.

  3. (3)

The Hamming graph $H(2,4)$ or its complement, and $G$ is a rank $3$ subgroup
of $\operatorname{AGL}(4,2)$.

  4. (4)

The Clebsch graph or its complement, and $G$ is a rank $3$ subgroup of
$\operatorname{AGL}(4,2)$.

Using the computational result that there exists no edge-transitive graph in
$\mathcal{F}(d)$ with $7\leq d\leq 10$ and of order at most $100$, one can
easily deduce which of the graphs in the families (1)–(4) above belongs also
to the family $\mathcal{F}(d)$ for some $d\geq 3$.

######  Corollary 2.8.

Let $\Gamma\in\mathcal{F}(d)$ be a $G$-edge-transitive graph for some $d\geq
3$. If $G$ is primitive on $V(\Gamma)$, then $\Gamma$ is isomorphic to one of
the graphs: $K_{6}$, the Petersen graph and its complement, and the Hamming
graph $H(2,4)$.

Finally, we also need a result of Lucchini [21] about core-free cyclic
subgroups (this serves as a key tool in [15, 2] as well). For the definition
of a core-free subgroup, see the remark following Definition 1.1.

######  Theorem 2.9.

([21]) If $C$ is a core-free cyclic proper subgroup of a group $G$, then
$|C|^{2}<|G|$.

##  3\. Nest graphs

In this section we review some previous results about Nest graphs, which were
obtained in [11, 17].

######  Lemma 3.1.

([11, Lemma 4]) Let $\Gamma=\operatorname{\mathcal{N}}(n;a,b,c;k)$ and suppose
that $c=a+b$ (in $\mathbb{Z}_{n}$). Then $\Gamma$ is edge-transitive if and
only if it is also arc-transitive.

The next result establishes some obvious isomorphisms.

######  Lemma 3.2.

([11, Lemma 5]) The graph $\operatorname{\mathcal{N}}(n;a,b,c;k)$ is
isomorphic to
$\operatorname{\mathcal{N}}(n;a^{\prime},b^{\prime},c^{\prime};k)$, where
$\\{a,b,c\\}=\\{a^{\prime},b^{\prime},c^{\prime}\\}$, as well as to any of the
graphs:

$\operatorname{\mathcal{N}}(n;a,b,c;-k),~{}\operatorname{\mathcal{N}}(n;-a,-b,-c;k)~{}\text{and}~{}\operatorname{\mathcal{N}}(n;-a,b-a,c-a;k).$

The graphs in the next lemma will be further studied in the next section.

######  Lemma 3.3.

([11, Lemma 6]) If $m\geq 3$ is an odd integer, then the graph
$\operatorname{\mathcal{N}}(2m;2,m,2+m;1)$ is arc-transitive having vertex
stabilisers of order $12$. Furthermore, the stabiliser of $u_{0}$ in
$\operatorname{Aut}(\Gamma)$ is the dihedral group $D_{6}$ of order $12$
generated by the involutions $\varphi$ and $\eta$ defined by

$u_{i}^{\varphi}=\begin{cases}u_{-i}&\text{if $i$ is even},\\\
v_{-i+1}&\text{if $i$ is odd}\end{cases}\quad\text{and}\quad
v_{i}^{\varphi}=\begin{cases}u_{-i+1}&\text{if $i$ is even},\\\
v_{-i+2}&\text{if $i$ is odd},\end{cases}$

and $u_{i}^{\eta}=u_{i}$ and $v_{i}^{\eta}=v_{i+m}$ for every
$i\in\mathbb{Z}_{n}$.

Suppose that $\Gamma$ is a $G$-edge-transitive Nest graph. In the next two
lemmas we consider block systems for $G$. A block system $\mathcal{B}$ is said
to be minimal if it is non-trivial, and no non-trivial block for $G$ is
contained properly in a block of $\mathcal{B}$ (by non-trivial we mean that
the block is neither a singleton subset nor the whole vertex set). We say that
$\mathcal{B}$ is normal if $\mathcal{B}=\operatorname{Orb}(N,V(\Gamma))$ for
some $N\lhd G$. Furthermore, we say that $\mathcal{B}$ is cyclic if any block
in $\mathcal{B}$ is contained in either $\\{u_{i}:i\in\mathbb{Z}_{n}\\}$ or
$\\{v_{i}:i\in\mathbb{Z}_{n}\\}$.

######  Lemma 3.4.

([17, Lemma 4.1]) Let $\Gamma$ be a $G$-edge-transitive Nest graph of order
$2n$ such that

$C<G,~{}C=\langle\rho\rangle,~{}\text{and}~{}\rho=(u_{0},u_{1},\ldots,u_{n-1})(v_{0},v_{1},\ldots,v_{n-1}),$

and let $\mathcal{B}$ be a cyclic block system for $G$ with blocks of size
$d$, $d<n/2$. Then the following hold.

  1. (1)

The kernel of the action of $G$ on $\mathcal{B}$ is equal to $C_{d}$ (the
subgroup of $C$ of order $d$).

  2. (2)

$\Gamma$ is a normal cover of $\Gamma/\mathcal{B}$.

  3. (3)

$\Gamma/\mathcal{B}$ is a $\bar{G}$-edge-transitive Nest graph of order
$2n/d$, where $\bar{G}$ is the image of $G$ induced by its action on
$\mathcal{B}$.

######  Remark.

Suppose that the graph $\Gamma$ in the lemma above is given as
$\Gamma=\operatorname{\mathcal{N}}(n;a,b,c;k)$ for $a,b,c,k\in\mathbb{Z}_{n}$.
Note that, then
$\Gamma/\mathcal{B}\cong\operatorname{\mathcal{N}}(n/d;f(a),f(b),f(c);f(k))$,
where $f$ is the homomorphism from $\mathbb{Z}_{n}$ to $\mathbb{Z}_{n/d}$ such
that $f(1)=1$.

######  Lemma 3.5.

([17, Lemma 4.2]) Let $\Gamma$ be a $G$-edge-transitive Nest graph of order
$2n$ such that

$C<G,~{}C=\langle\rho\rangle,~{}\text{and}~{}\rho=(u_{0},u_{1},\ldots,u_{n-1})(v_{0},v_{1},\ldots,v_{n-1}),$

and let $\mathcal{B}$ be a non-cyclic block system for $G$ with blocks of size
$d$. Then the following hold.

  1. (1)

The number $d$ is even and any block in $\mathcal{B}$ is a union of two
$C_{d/2}$-orbits.

  2. (2)

The group $C$ acts transitively on $\mathcal{B}$ and the kernel of the action
of $C$ on $\mathcal{B}$ is equal to $C_{d/2}$.

  3. (3)

If $d>2$ and $\mathcal{B}$ is minimal, then $\mathcal{B}$ is normal.

##  4\. A property of the graphs $\operatorname{\mathcal{N}}(2m;2,m,2+m;1)$,
$m$ is odd

In this section we give the following characterisation of the Nest graphs in
the title. As we said in the introduction, this was mentioned already in [11]
without a proof.

######  Proposition 4.1.

Let $\Gamma=\operatorname{\mathcal{N}}(n;a,b,c;k)$ be an edge-transitive graph
such that $n>8$ and suppose that there exists a non-identity automorphism of
$\Gamma$, which fixes all vertices $u_{i}$, $i\in\mathbb{Z}_{n}$. Then
$\Gamma\cong\operatorname{\mathcal{N}}(2m;2,m,2+m;1)$ for some odd number $m$.

We prove first an auxiliary lemma.

######  Lemma 4.2.

Let $\Gamma=\operatorname{\mathcal{N}}(2m;a,m,a+m;k)$, where $m>2$, $a=2$ or
$m-2$, and $k=1$ or $m-1$. Then $\Gamma$ is edge-transitive if and only if $m$
is odd and $\Gamma\cong\operatorname{\mathcal{N}}(2m;2,m,2+m;1)$.

###### Proof.

The “if” part follows from Lemma 3.3.

For the “only if” part, assume that $\Gamma$ is edge-transitive. Applying
Lemma 3.2 to $\Gamma$, we find that

$\Gamma\cong\Gamma^{\prime}:=\operatorname{\mathcal{N}}(2m;2,m,2+m;k),$

where $k=1$ or $m-1$. We have to show that $m$ is odd and $k=1$.

Assume on the contrary that $m$ is even or $k=m-1$. Moreover, let us choose
$m$ so that it is the smallest number for which this happens. A quick check
with the computer algebra package Magma [4] shows that $m\geq 12$.

Define the binary relation $\sim$ on $V(\Gamma^{\prime})$ by letting $u\sim v$
whenever $|\Gamma^{\prime}(u)\cap\Gamma^{\prime}(v)|=4$ for any $u,v\in
V(\Gamma^{\prime})$. Using that $m\geq 12$, it is not hard to show that $\sim$
is an equivalence relation with classes in the form

$B_{i}:=\\{u_{i},u_{i+m},v_{i+1},v_{i+1+m}\\},~{}i\in\mathbb{Z}_{n}.$

Clearly, $\sim$ is invariant under $\operatorname{Aut}(\Gamma^{\prime})$, so
the classes above form a block system for
$\operatorname{Aut}(\Gamma^{\prime})$. Part of the graph with $k=m-1$ is shown
in Figure 1.

$u_{i-2}$$u_{i-1}$$u_{i}$$u_{i+1}$$u_{i+2}$$u_{i-2+m}$$u_{i-1+m}$$u_{i+m}$$u_{i+1+m}$$u_{i+2+m}$$v_{i-1}$$v_{i}$$v_{i+1}$$v_{i+2}$$v_{i+3}$$v_{i-1+m}$$v_{i+m}$$v_{i+1+m}$$v_{i+2+m}$$v_{i+3+m}$
Figure 1. The Nest graph $\operatorname{\mathcal{N}}(2m;2,m,2+m,m-1)$.

Let $K$ be the kernel of the action of $\operatorname{Aut}(\Gamma^{\prime})$
on the latter block system. We prove next that $K$ is faithful on every block.
Suppose that $g$ fixes pointwise the block $B_{i}$ for some
$i\in\mathbb{Z}_{n}$. Any pair of vertices in $B_{i+1}$ are contained in a
unique $4$-cycle intersecting $B_{i}$ at two vertices (see Figure 1). This
means that $g$ maps any pair to itself, implying that $g$ fixes pointwise
$B_{i+1}$. Repeating the argument, we conclude that $g$ fixes pointwise each
block $B_{i}$, i.e., $g$ is the identity automorphism.

Let $n=2m$, $C=\langle\rho\rangle$, where
$\rho=(u_{0},u_{1},\ldots,u_{n-1})(v_{0},v_{1},\ldots,v_{n-1})$. Using the
facts that $K$ is faithful on every block $B_{i}$ and the quotient graph
$\Gamma/\mathcal{B}$ is an $n/2$-cycle whose automorphism group is isomorphic
to the dihedral group $D_{n/2}$ of order $n$, we obtain the bound

$|\operatorname{Aut}(\Gamma^{\prime})|\leq|K|\cdot n=24n.$

Thus $|C|^{2}=n^{2}\geq|\operatorname{Aut}(\Gamma^{\prime})|$ because
$n=2m\geq 24$. By Theorem 2.9, $C$ has a non-trivial core in
$\operatorname{Aut}(\Gamma^{\prime})$, let this core be denoted by $N$.

Assume first that $|N|$ is even. Then as $C_{2}$ is characteristic in $N$ and
$N\lhd\operatorname{Aut}(\Gamma^{\prime})$, we obtain that
$C_{2}\lhd\operatorname{Aut}(\Gamma^{\prime})$. Thus
$\operatorname{Orb}(C_{2},V(\Gamma))$ is a block system for
$\operatorname{Aut}(\Gamma^{\prime})$. But this is impossible because $u_{0}$
has one neighbour from the orbit $\\{u_{1},u_{1+m}\\}$ and two from the orbit
$\\{v_{0},v_{m}\\}$.

Let $|N|$ be odd and choose an odd prime divisor $p$ of $|N|$. It follows as
above that $C_{p}\lhd\operatorname{Aut}(\Gamma^{\prime})$. Clearly, $p$
divides $m$.

Assume that $m=p$ or $2p$. If $m=p$, then by our initial assumptions, $k=p-1$.
But this means that the edge $\\{v_{0},v_{k}\\}$ is contained in a
$C_{p}$-orbit, contradicting that
$C_{p}\lhd\operatorname{Aut}(\Gamma^{\prime})$ and $\Gamma^{\prime}$ is edge-
transitive. If $m=2p$, then $u_{0}$ has one neighbour from the $C_{p}$-orbit
$\\{u_{4i+1}:0\leq i\leq p-1\\}$ and two from the $C_{p}$-orbit
$\\{v_{4i}:0\leq i\leq p-1\\}$ (namely, $v_{0}$ and $v_{2+m}=v_{2+2p}$), which
is a contradiction again.

Let $m>2p$. By Lemma 3.4(3) and the remark after the lemma,

$\Gamma^{\prime}/C_{p}\cong\operatorname{\mathcal{N}}(2m/p;f(2),f(m),f(2+m),f(k)),$

where $f$ is the homomorphism from $\mathbb{Z}_{2m}$ to $\mathbb{Z}_{2m/p}$
such that $f(1)=1$. Since $m>2p$ and $p$ is odd, it follows that

$f(2)=2,~{}f(m)=m/p~{}\text{and}~{}f(2+m)=2+m/p.$

Furthermore, $f(k)=1$ if $k=1$ and $f(k)=m/p-1$ if $k=m-1$. By the minimality
of $m$, we see that $m/p$ is odd and $f(k)=1$. This, however, contradicts that
$m$ is even or $k=m-1$. ∎

###### Proof of Proposition 4.1.

Let $H$ and $N$ be the setwise and the pointwise stabiliser, respectively, of
the set $\\{u_{i}:i\in\mathbb{Z}_{n}\\}$ in $\operatorname{Aut}(\Gamma)$. Then
$N\neq 1$ and $N\lhd H$. It follows that the $N$-orbits contained in
$V:=\\{v_{i}:i\in\mathbb{Z}_{n}\\}$ form a block system for the action of $H$
on $V$, implying that $\operatorname{Orb}(N,V)=\operatorname{Orb}(C_{d},V)$
for some $d>1$. This yields that $n=2m$ and we may write w.l.o.g. that

$a<m,~{}b=m,~{}c=a+m,~{}\text{and}~{}k<m.$

Let $\eta$ be the permutation of the vertex set acting as

$u_{i}^{\eta}=u_{i}~{}\text{and}~{}v_{i}^{\eta}=v_{i+m}~{}(i\in\mathbb{Z}_{n}).$

It is easy to check that $\eta\in\operatorname{Aut}(\Gamma)$.

Note that, by Lemma 3.1, $\Gamma$ is arc-transitive, so
$\operatorname{Aut}(\Gamma)_{u_{0}}$ is transitive on $\Gamma(u_{0})$. Let
$s=|\Gamma(v_{0})\cap\Gamma(v_{m})|$. It is easy to see that $s\geq 4$. Define
the graph $\Delta$ as follows:

$V(\Delta)=\Gamma(u_{0})~{}\text{and}~{}E(\Delta)=\\{\\{w,w^{\prime}\\}:|\Gamma(w)\cap\Gamma(w^{\prime})|=s\\}.$

Note that $\Delta$ is vertex-transitive, in particular, it is regular.

Assume for the moment that $u_{1}$ and $u_{-1}$ are adjacent in $\Delta$. This
means $|\Gamma(u_{1})\cap\Gamma(u_{-1})|=s\geq 4$. Since
$\Gamma(u_{1})\cap\Gamma(u_{-1})\cap\\{u_{i}:i\in\mathbb{Z}_{n}\\}=\\{u_{0}\\}$,
we conclude that

$|\\{1,1+a,1+m,1+a+m\\}\cap\\{-1,-1+a,-1+m,-1+a+m\\}|\geq 3.$ (2)

At least one of $1$ and $1+m$ is in the intersection. If it is $1$, then
$1=-1+a$ or $-1+a+m$ because $n>4$. As $a<m$, we find that $a=2$. Similarly,
if $1+m$ is in the intersection, then $1+m=-1+a$ or $-1+a+m$, and we find
again that $a=2$. Now, substituting $a=2$ in (5), a contradiction arises
because $n>8$.

Therefore, $u_{1}$ and $u_{-1}$ are not adjacent in $\Delta$. Using also that
$\eta\in\operatorname{Aut}(\Gamma)$, see above, we obtain that $u_{1}$ must be
adjacent with $v_{0}$ or $v_{a}$.

Assume first that $u_{1}$ and $v_{0}$ are adjacent. Then
$\Gamma(u_{1})\cap\Gamma(v_{0})=\\{u_{0},u_{2},v_{k},v_{-k}\\}$, hence
$2\in\\{0,n-a,m,n-a+m\\}$ and $k\in\\{1,1+a,1+m,1+a+m\\}$. Since $a,k<m$ and
$n>4$, we find in turn that $a=m-2$, and $k=1$ or $m-1$.

Now, if $u_{1}$ and $v_{a}$ are adjacent, then
$\Gamma(u_{1})\cap\Gamma(v_{a})=\\{u_{0},u_{2},v_{a+k},v_{a-k}\\}$, whence
$2\in\\{a,0,a+m,m\\}$ and $a+k\in\\{1,1+a,1+m,1+a+m\\}$. Since $a,k<m$ and
$n>4$, we find in turn that $a=2$, and $k=1$ or $m-1$.

To sum up, $a=2$ or $m-2$ and $k=1$ or $m-1$, and so the proposition follows
from Lemma 4.2. ∎

######  Corollary 4.3.

Let $\Gamma$ be a $G$-edge-transitive Nest graph of order $2n$ such that $n>8$
and

$C<G,~{}C=\langle\rho\rangle,~{}\text{and}~{}\rho=(u_{0},u_{1},\ldots,u_{n-1})(v_{0},v_{1},\ldots,v_{n-1}),$

and suppose that $\operatorname{Orb}(C_{n/2},V(\Gamma))$ is a block system for
$G$. Then $C_{n/2}\lhd G$.

###### Proof.

Let $K$ be the kernel of the action of $G$ on the block system
$\operatorname{Orb}(C_{n/2},V(\Gamma))$, and let $K^{*}$ and $(C_{n/2})^{*}$
denote the image of $K$ and $C_{n/2}$, respectively, induced by their action
on $U:=\\{u_{i}:i\in\mathbb{Z}_{n}\\}$. Since the subgraph of $\Gamma$ induced
by $U$ is a cycle of length $n>8$, it follows that $(C_{n/2})^{*}$ is
characteristic in $K^{*}$. Therefore, if $K$ is faithful on $U$, then
$C_{n/2}$ is characteristic in $K$ and as $K\lhd G$, we obtain that
$C_{n/2}\lhd G$, as required.

If $K$ is not faithful on $U$, then by Proposition 4.1, $n=2m$, $m$ is odd,
and $\Gamma\cong\Gamma^{\prime}:=\operatorname{\mathcal{N}}(2m;2,m,2+m;1)$.
Consider the group $\langle C,\varphi,\eta\rangle$, where $\varphi$ and $\eta$
are defined in Lemma 3.3. This is transitive on $V(\Gamma^{\prime})$ and also
contains the stabiliser of $u_{0}$ in $\operatorname{Aut}(\Gamma^{\prime})$,
therefore, $\operatorname{Aut}(\Gamma^{\prime})=\langle
C,\varphi,\eta\rangle$. A straightforward computation shows that
$\varphi\rho^{2}\varphi=\rho^{-2}$ and $\eta\rho^{2}=\rho^{2}\eta$, and hence
$C_{n/2}\lhd\operatorname{Aut}(\Gamma^{\prime})$. All these show that
$C_{n/2}\lhd G$ holds in this case as well. ∎

##  5\. Proof Theorem 1.2

Throughout this section we keep the following notation.

######  Hypothesis 5.1.

> $\Gamma=\operatorname{\mathcal{N}}(n;a,b,c;k)$ is a Nest graph of order
> $2n$, $n\geq 4$,
>  $C=\langle\rho\rangle$, where
> $\rho=(u_{0},u_{1},\ldots,u_{n-1})(v_{0},v_{1},\ldots,v_{n-1}),$
>  $G\leq\operatorname{Aut}(\Gamma)$ such that $\rho\in G$, $G$ acts
> transitively on $E(\Gamma)$, and $\operatorname{core}_{G}(C)=1$.

Instead of Theorem 1.2 we show the following slightly more stronger theorem.
The proof will be given in the end of the section.

######  Theorem 5.2.

Assuming Hypothesis 5.1, $\Gamma$ is isomorphic to one of the graphs:
$\operatorname{\mathcal{N}}(5;1,2,3;2)$,
$\operatorname{\mathcal{N}}(8;1,3,4;3)$,
$\operatorname{\mathcal{N}}(8;1,2,5;3)$ and
$\operatorname{\mathcal{N}}(12;2,4,8;5)$.

We start with a computational result, which we retrieved from [11, Table 1]
with the help of Magma [4]. Here we use the obvious facts that $C$ is also
core-free in $\operatorname{Aut}(\Gamma)$ and that
$\operatorname{Aut}(\Gamma)$ is primitive whenever so is $G$.

######  Lemma 5.3.

Assuming Hypothesis 5.1, if $n\leq 50$, then the following hold.

  1. (1)

$\Gamma$ is isomorphic to one of the graphs:

$\operatorname{\mathcal{N}}(5;1,2,3;2),~{}\operatorname{\mathcal{N}}(8;1,3,4;3),~{}\operatorname{\mathcal{N}}(8;1,2,5;3)~{}\text{and}~{}\operatorname{\mathcal{N}}(12;2,4,8;5).$

  2. (2)

$G$ is either primitive and $\Gamma\cong\operatorname{\mathcal{N}}(5;1,2,3;2)$
or $\operatorname{\mathcal{N}}(8;1,3,4;3)$; or for
$N:=\operatorname{soc}(\operatorname{Aut}(\Gamma))$,
$N\cong\mathbb{Z}_{2}^{2}$ if $n=8$ and $N\cong\mathbb{Z}_{2}^{4}$ if $n=12$,
and the $N$-orbits have length $4$.

The existence of a non-trivial non-cyclic block system is established next.

######  Lemma 5.4.

Assuming Hypothesis 5.1, suppose that $n>8$. Then $G$ admits a non-trivial
non-cyclic block system.

###### Proof.

Observe that, if $G$ is primitive, then Corollary 2.8 shows that
$\Gamma\cong\operatorname{\mathcal{N}}(5;1,2,3;2)$ or
$\operatorname{\mathcal{N}}(8;1,3,4;3)$. As $n>8$, $G$ is imprimitive.

Let $\mathcal{B}$ be a non-trivial block system with blocks of size $d$. If
$\mathcal{B}$ is cyclic, then by Lemma 3.4(1) and Corollary 4.3, $C_{d}\lhd
G$, where $C_{d}$ is the subgroup of $C$ of order $d$. This contradicts our
assumption that $\operatorname{core}_{G}(C)=1$, so $\mathcal{B}$ is non-
cyclic. ∎

In the next two lemmas we study non-cyclic block systems with blocks of size
$2$.

######  Lemma 5.5.

Assuming Hypothesis 5.1, suppose that $n>50$ and $\mathcal{B}$ is a non-cyclic
block system for $G$ with blocks of size $2$. Then $\Gamma/\mathcal{B}$ has
valency $12$.

###### Proof.

Let $K$ be the kernel of the action of $G$ on $\mathcal{B}$, and for a
subgroup $X\leq G$, denote by $\bar{X}$ the image of $X$ induced by its action
on $\mathcal{B}$. For a block $B\in\mathcal{B}$, we write
$B=\\{u_{B},v_{B}\\}$, where $u_{B}\in\\{u_{i}:i\in\mathbb{Z}_{n}\\}$ and by
$v_{B}\in\\{v_{i}:i\in\mathbb{Z}_{n}\\}$, and define the permutation $\tau$ of
$V(\Gamma)$ as

$\tau:=\prod_{B\in\mathcal{B}}(u_{B}\,v_{B}).$ (3)

Observe that $\tau$ commutes with any element of $G$.

Now define the graph $\Gamma^{\prime}$ as

$V(\Gamma^{\prime}):=V(\Gamma)~{}\text{and}~{}E(\Gamma^{\prime}):=\\{\\{u_{0},u_{1}\\}^{x}:x\in\langle
G,\tau\rangle\\}$ (4)

Then $E(\Gamma)=\\{\\{u_{0},u_{1}\\}^{x}:x\in G\\}\subseteq
E(\Gamma^{\prime})$. Also,
$\langle\tau,G\rangle\leq\operatorname{Aut}(\Gamma^{\prime})$, hence
$\Gamma^{\prime}$ is both vertex- and edge-transitive. Since $\tau$ commutes
with every element of $G$, it follows that $E(\Gamma^{\prime})=E(\Gamma)\cup
E(\Gamma)^{\tau}$ and $E(\Gamma)=E(\Gamma)^{\tau}$ or $E(\Gamma)\cap
E(\Gamma)^{\tau}=\emptyset$. Notice that

$\Gamma/\mathcal{B}=\Gamma^{\prime}/\mathcal{B},$

hence we are done if show that $\Gamma^{\prime}/\mathcal{B}$ has valency $12$.

Denote by $d$ and $d^{\prime}$ the valency of $\Gamma^{\prime}$ and
$\Gamma^{\prime}/\mathcal{B}$, respectively. Now,
$d=|E(\Gamma^{\prime})|/n=6\frac{|E(\Gamma^{\prime})|}{|E(\Gamma)|}$. This
shows that $d=6$ if $E(\Gamma)=E(\Gamma^{\prime})$, and $d=12$ otherwise.

Assume for the moment that $d=6$, i.e., $E(\Gamma)=E(\Gamma^{\prime})$. In
this case $\tau\in K$, hence $\mathcal{B}$ is normal and $\Gamma^{\prime}$ is
a normal $r$-cover of $\Gamma^{\prime}/\mathcal{B}$ and $r=1$ or $r=2$.

If $r=2$, then $d^{\prime}=3$. As $n>50$, this is impossible due to Lemma 2.2.
Here we use the facts that $\Gamma^{\prime}/\mathcal{B}$ is edge-transitive
and $\bar{C}$ is regular on $V(\Gamma^{\prime}/\mathcal{B})$. It is well-known
that an edge-transitive circulant graph is also arc-transitive. Thus $r=1$ and
$d^{\prime}=6$. As $n>50$, Lemma 2.3 can be applied to
$\Gamma^{\prime}/\mathcal{B}$ and $\bar{C}$. This says that
$\operatorname{Aut}(\Gamma^{\prime}/\mathcal{B})$ has a normal subgroup $N$
such that

  1. (1)

$N=\bar{C}$, or

  2. (2)

$n\equiv 4\\!\\!\pmod{8}$ and $N=\bar{C}_{n/4}$, or

  3. (3)

$N\cong\mathbb{Z}_{3}^{\ell}$ for $\ell\geq 2$ and $\bar{C}_{3}\leq N$.

In case (1), $N<\bar{G}$, hence $KC\lhd G$. The condition $r=1$ yields that
$K=\langle\tau\rangle$. Thus $KC$ is abelian and $\langle x^{2}:x\in
KC\rangle=C_{n}$ if $n$ is odd and $C_{n/2}$ if $n$ is even. Using that the
latter group is characteristic in $KC$ and $KC\lhd G$, we obtain that
$\operatorname{core}_{G}(C)\neq 1$, a contradiction.

In case (2), $N<\bar{G}$, hence $KC_{n/4}\lhd G$. Since $KC$ is abelian, it
follows that $C_{n/4}$ is characteristic in $KC$, implying that $C_{n/4}\lhd
G$, a contradiction.

In case (3), $\bar{C}_{3}\leq\bar{G}\cap N$. Since $\bar{G}\cap N\lhd\bar{G}$,
it follows that $G$ contains a normal subgroup $M$ such that
$M=\langle\tau\rangle\times S$, where $S\cong\mathbb{Z}_{3}^{\ell^{\prime}}$
for some $\ell^{\prime}\geq 1$. Thus $S$ is normal in $G$, and we obtain that
$\operatorname{Orb}(S,V(\Gamma))$ is a non-trivial cyclic block system for
$G$. This contradicts Lemma 5.4, and we conclude that $d=12$.

The graph $\Gamma^{\prime}$ is a normal $r$-cover of
$\Gamma^{\prime}/\mathcal{B}$, where $r=1$ or $r=2$, and we have
$d^{\prime}=d/r=12/r$. If $r=2$, then $u_{0}$ is adjacent with $6$ vertices
that are contained in the set $\\{u_{i}:i\in\mathbb{Z}_{n}\\}$. It follows
from the definition of $\Gamma^{\prime}$ that this impossible. Thus $r=1$, and
so $d^{\prime}=12$. ∎

######  Lemma 5.6.

Assuming Hypothesis 5.1, suppose that $n>50$ and $\mathcal{B}$ is a non-cyclic
block system for $G$ with blocks of size $2$. Then there is a normal non-
cyclic block system for $G$ with blocks of size $4$.

###### Proof.

Let $K$ be the kernel of the action of $G$ on $\mathcal{B}$, and for a
subgroup $X\leq G$, denote by $\bar{X}$ the image of $X$ induced by its action
on $\mathcal{B}$. For the sake of simplicity we write $\bar{\Gamma}$ for
$\Gamma/\mathcal{B}$.

By Lemma 5.5, $\bar{\Gamma}$ has valency $12$. This implies that $K=1$. As
$\bar{C}\leq\operatorname{Aut}(\bar{\Gamma})$ and it is regular on
$V(\bar{\Gamma})$, Theorem 2.1 can be applied to $\bar{\Gamma}$ and $\bar{C}$.
As $n>50$, $\bar{\Gamma}$ cannot be the complete graph. Also, if
$\bar{C}\lhd\operatorname{Aut}(\bar{\Gamma})$, then $C\lhd G$ because $K=1$.
This is also impossible, hence $\bar{\Gamma}$ is in one of the families (c)
and (d) of Theorem 2.1.

Case 1. $\bar{\Gamma}$ is in family (c).

In this case $\operatorname{Orb}(\bar{C}_{d},V(\bar{\Gamma}))$ is a block
system for $\operatorname{Aut}(\bar{\Gamma})$, hence for $\bar{G}$ as well,
where $d\in\\{2,3,4,6\\}$. Let $N$ be the unique subgroup of $G$ for which
$\bar{N}$ is the kernel of the action of $\bar{G}$ on
$\operatorname{Orb}(\bar{C}_{d},V(\bar{\Gamma}))$. Note that $N\lhd G$ and
$N\cong\bar{N}$ because $K=1$. Let
$\mathcal{B}^{\prime}=\operatorname{Orb}(N,V(\Gamma))$. It follows that
$\mathcal{B}^{\prime}$ is non-cyclic and it has blocks of size $2d$.

Let $d=2$. Then $\mathcal{B}^{\prime}$ is normal with blocks of size $4$, so
the conclusion of the lemma holds.

Let $d=3$. Then the Sylow $3$-subgroup of $\bar{N}$ is normal in $\bar{G}$. It
follows in turn that, the Sylow $3$-subgroup of $N$ is normal in $G$, the
orbits of the latter subgroup form a non-trivial cyclic block system for $G$.
This contradicts Lemma 5.4.

Let $d=4$. Then $\bar{\Gamma}$ has valency $3$. It follows from Lemma 2.2 that
$n\leq 6$, but this is excluded.

Finally, let $d=6$. Let $\tau$ be the permutation of $V(\Gamma)$ defined in
(3) and $\Gamma^{\prime}$ be the graph defined in (4). Let $\Delta$ be the
subgraph of $\Gamma^{\prime}$ induced by the set $u_{0}^{N}\cup u_{1}^{N}$. It
is not hard to show that $\Delta$ is a bipartite graph, it has valency $6$,
and it is also edge-transitive. Moreover, if $B\in\mathcal{B}$ such that
$u_{0}\notin B$ and $B\subset u_{0}^{N}\cup u_{1}^{N}$, then

$|\Delta(u_{0})\cap B|=1.$ (5)

Since $\langle\tau\rangle\times C_{6}\leq\operatorname{Aut}(\Delta)$, it
follows that $\Delta$ is uniquely determined by $\Delta(u_{0})$. It follows
from the definition of $\Gamma^{\prime}$ that
$|\Gamma^{\prime}(u_{0})\cap\\{u_{i}:i\in\mathbb{Z}_{n}\\}|=4$. Therefore,
replacing $u_{0}^{N}\cup u_{1}^{N}$ with $u_{0}^{N}\cup u_{n-1}^{N}$ if
necessary, we may assume w.l.o.g. that
$|\Delta(u_{0})\cap\\{u_{i}:i\in\mathbb{Z}_{n}\\}|\leq 2$. This together with
(5) show that there are $6$ possibilities for $\Delta$. A computation with
Magma [4] shows that none of these $6$ graphs is edge-transitive.

Case 2. $\bar{\Gamma}$ is in family (d).

We finish the proof by showing this case does not occur. Theorem 2.1 shows
that $\mathcal{B}_{1}:=\operatorname{Orb}(\bar{C}_{d},V(\bar{\Gamma}))$ and
$\mathcal{B}_{2}:=\operatorname{Orb}(\bar{C}_{n/d},,V(\bar{\Gamma}))$ are
blocks for $\bar{G}$ for some divisor $d$ of $n$ such that $d\in\\{4,5,7\\}$
and $\gcd(d,n/d)=1$. Furthermore,

$\bar{C}_{d}\times\bar{C}_{n/d}<\bar{G}\leq\operatorname{Aut}(\Gamma^{\prime})=G_{1}\times
G_{2},$

where $\bar{C}_{d}\leq G_{1}$, $G_{1}\cong S_{d}$, $\bar{C}_{n/d}<G_{2}$ and
$G_{2}\cong\operatorname{Aut}(\Gamma^{\prime}/\mathcal{B}_{1})$.

Let $d=4$. Then $\bar{\Gamma}/\mathcal{B}_{1}$ has valency $4$. Using also
that $n/d$ is odd and that $n>20$, it follows from Lemma 2.2 that
$\bar{C}_{n/d}\lhd\bar{G}$, hence $C_{n/d}\lhd G$, a contradiction.

Let $d=5$. Then $\bar{\Gamma}/\mathcal{B}_{1}$ has valency $3$, hence $n\leq
30$ by Lemma 2.2, which is excluded.

Finally, let $d=7$. Then $\bar{\Gamma}/\mathcal{B}_{1}$ is a cycle of length
$n/7$, implying that $\bar{C}_{n/d}\lhd\bar{G}$, so $C_{n/d}\lhd G$, a
contradiction. ∎

Before the proof of Theorem 5.2 we need two more lemmas dealing with non-
cyclic block systems with blocks of size at least $4$.

######  Lemma 5.7.

Assuming Hypothesis 5.1, suppose that $n>50$ and $\mathcal{B}$ is a minimal
non-cyclic block system for $G$ with blocks of size at least $4$, and let
$B\in\mathcal{B}$ be any block. Then the permutation group of $B$ induced by
$G_{\\{B\\}}$ is an affine group.

###### Proof.

For a subgroup $X\leq G_{\\{B\\}}$, denote by $X^{*}$ the image of $X$ induced
by its action on $B$. As $B$ is minimal, $(G_{\\{B\\}})^{*}$ is a primitive
permutation group. Also, $(C_{\\{B\\}})^{*}$ is a semiregular cyclic subgroup
of $(G_{\\{B\\}})^{*}$ with $2$ orbits, hence Theorem 2.4 can be applied to
$(G_{\\{B\\}})^{*}$. This shows that $(G_{\\{B\\}})^{*}$ is either an affine
group or it is one of the groups in the families (a)-(f) in part (2) of
Theorem 2.4. Assume that the latter case occurs. We drive in three steps that
this leads to a contradiction. Let $K$ be the kernel of the action of $G$ on
$\mathcal{B}$.

Step 1. $K$ acts faithfully on every block in $\mathcal{B}$.

Since $K\lhd G_{\\{B\\}}$, it follows that $K^{*}\lhd(G_{\\{B\\}})^{*}$. By
Corollary 2.5, $K^{*}$ is primitive and belongs to the same family as
$(G_{\\{B\\}})^{*}$.

Assume on the contrary that $K$ is not faithful on every block. Using the
connectedness of $\Gamma$, it is easy to show that there are blocks
$B,B^{\prime}$ in $\mathcal{B}$ with the following properties: The kernel of
the action of $K$ on $B$ is non-trivial on $B^{\prime}$, and $\Gamma$ has an
edge $\\{w,w^{\prime}\\}$ such that $w\in B$ and $w^{\prime}\in B^{\prime}$.
Denote by $N$ the latter kernel. Now as $N\lhd K$ and $K$ is primitive on
$B^{\prime}$, $N$ is transitive on $B^{\prime}$. Thus the orbit
$(w^{\prime})^{N}=B^{\prime}$, and so $w$ is adjacent with any vertex in
$B^{\prime}$. Since $\mathcal{B}$ is normal, it follows that the subgraph of
$\Gamma$ induced by $B\cup B^{\prime}$ is isomorphic to the complete bipartite
graph $K_{m,m}$, where $m=|B|$. On the other hand, $m\geq 6$, showing that
$\Gamma\cong K_{6,6}$, a contradiction.

Denote by $B$ and $B^{\prime}$ the blocks containing $u_{0}$ and $u_{1}$,
respectively.

Step 2. The action of $K$ on $B$ is equivalent with its action on
$B^{\prime}$.

Assume on the contrary that the actions are inequivalent. Due to Lemma 2.6(2),
$K$ belongs to family (c) in Theorem 2.4(2) with $d\geq 4$, and the elements
in $B$ and $B^{\prime}$ correspond to the points and the hyperplanes of the
projective geometry $\operatorname{PG}(d-1,q)$, respectively. The set
$B^{\prime}$ splits into two $K_{u_{0}}$-orbits of lengths

$(q^{d-1}-1)/(q-1)~{}\text{and}~{}q(q^{d-1}-1)/(q-1).$

The first orbit consists of the hyperplanes of $\operatorname{PG}(d-1,q)$
through the point represented by $u_{0}$, and the second orbit consists of the
remaining hyperplanes. Clearly, the minimum of these numbers is bounded above
by the valency of $\Gamma$, implying that $q^{d-1}-1\leq 6(q-1)$, and hence
$q^{d-2}<6$. This is impossible because $d\geq 4$.

Step 3. $\operatorname{core}_{G}(C)\neq 1$.

Since $K$ acts equivalently on $B$ and $B^{\prime}$, it follows that
$K_{u_{0}}=K_{v}$ for some vertex $v\in B^{\prime}$ (see [8, Lemma 1.6B]).
Define the binary relation $\sim$ on $V(\Gamma)$ by letting $u\sim v$ if and
only if $K_{u}=K_{v}$. It is not hard to show, using that $K\lhd G$, that
$\sim$ is a $G$-congruence (see [8, Exercise 1.5.4]), and so there is a block
for $G$ containing $u_{0}$ and $v$. Also, as $K$ is not regular, this block is
non-trivial, and this shows that $v\neq u_{1}$.

By Lemma 2.6(1), $K$ is $2$-transitive on $B^{\prime}$, unless
$|B^{\prime}|=10$, $K=A_{5}$ or $S_{5}$, and it has subdegrees $1,3$ and $6$.

Assume first that $K$ is $2$-transitive on $B^{\prime}$. Then the orbit
$u_{1}^{K_{u_{0}}}=u_{1}^{K_{v}}=|B^{\prime}|-1$ and each vertex in
$u_{1}^{K_{v}}$ is adjacent with $u_{0}$. Hence $u_{0}$ has $|B^{\prime}|-1$
neighbours in $B^{\prime}$. On the other hand, as $\mathcal{B}$ is normal,
this number divides $6$, so $|B|=|B^{\prime}|=4$, contradicting that
$G_{\\{B\\}}^{*}$ is an almost simple group.

We are left with the case that $|B^{\prime}|=10$, $K=A_{5}$ or $S_{5}$, and it
has subdegrees $1,3$ and $6$. Consequently, $u_{0}$ has $3$ or $6$ neighbours
in $B^{\prime}$.

If $u_{0}$ has $6$ neighbours, then it is clear that $n=10$, which is
excluded.

Now assume that $u_{0}$ has $3$ neighbours in $B^{\prime}$. In this case
$\Gamma$ is a normal $3$-cover of a cycle of length $n/5$. Since
$\Gamma/\mathcal{B}$ is a cycle of length $n/5$, it follows that
$|G|\leq|K|\cdot 2n/5=48n$. Using that $n>50$, Theorem 2.9 shows that
$\operatorname{core}_{G}(C)\neq 1$. ∎

######  Lemma 5.8.

Assuming Hypothesis 5.1, suppose that $n>50$ and $\mathcal{B}$ is a minimal
non-cyclic block system for $G$ with blocks of size at least $4$. Then the
blocks have size $4$.

###### Proof.

Let $K$ be the kernel of the action of $G$ on $\mathcal{B}$, and let
$B\in\mathcal{B}$ be the block containing $u_{0}$. Denote by
$(G_{\\{B\\}})^{*}$ the permutation group of $B$ induced by $G_{\\{B\\}}$. By
Lemma 5.7, $(G_{\\{B\\}})^{*}$ is an affine group, and thus it is one of the
groups in the families (a)–(d) in part (1) of Theorem 2.4. In particular,
$|B|\in\\{4,8,16\\}$. Assume on the contrary that $|B|>4$. By Lemma 3.5,
$\mathcal{B}$ is normal, hence $\Gamma$ is a normal $r$-cover of
$\Gamma/\mathcal{B}$ for $r\in\\{1,2,3\\}$.

Case 1. $r=1$.

In this case $K$ is regular on every block, in particular,
$K\cong\mathbb{Z}_{2}^{4}$ or $\mathbb{Z}_{2}^{5}$. On the other hand, by
Lemma 3.5(2), $C_{|B|/2}<K$, a contradiction.

Case 2. $r=2$.

In this case $\Gamma/\mathcal{B}$ has valency $3$. It follows from Lemma 2.2
that $n\leq 48$, but this is excluded.

Case 3. $r=3$.

Then $\Gamma/\mathcal{B}$ is a cycle of length $2n/|B|$. This implies that the
action of $G_{u_{0}}$ on $\Gamma(u_{0})$ admits a block system consisting of
two blocks of size $3$. Consequently, the restriction of $G_{u_{0}}$ to
$\Gamma(u_{0})$ is a $\\{2,3\\}$-group. This together with the fact that
$\Gamma$ is connected yield that $G_{u_{0}}$ is also a $\\{2,3\\}$-group. Now
checking the stabilisers in part (1) of Theorem 2.4, we find that $|B|=16$ and

$(G_{\\{B\\}})^{*}_{u_{0}}\cong(\mathbb{Z}_{3}\times\mathbb{Z}_{3})\rtimes\mathbb{Z}_{4}~{}\text{or}~{}(S_{3}\times
S_{3})\rtimes\mathbb{Z}_{2}$ (6)

Assume for the moment $K$ is not faithful on $B$. Then there exist adjacent
blocks $B^{\prime}$ and $B^{\prime\prime}$ such that the apkernel of the
action of $K$ on $B^{\prime}$ is non-trivial on $B^{\prime\prime}$. Denote
this kernel by $L$. The $L$-orbits contained in $B^{\prime\prime}$ have the
same size, which is equal to $2^{s}$ for some $1\leq s\leq 4$. On the other
hand, for $w\in B^{\prime}$, the set $\Gamma(w)\cap B^{\prime\prime}$ is
$L$-invariant, implying that $|\Gamma(w)\cap B^{\prime\prime}|$ is equal to
some power of $2$, a contradiction. Thus $K$ is faithful on $B$.

The group $K$ contains a normal subgroup $E$ such that
$E\cong\mathbb{Z}_{2}^{4}$. Note that
$\mathcal{B}=\operatorname{Orb}(E,V(\Gamma))$. Let $P$ be the Sylow
$3$-subgroup of $G_{\\{B\\}}$. Since $\Gamma/\mathcal{B}$ is a cycle, it
follows that $P\leq K$. This also shows that $P\cong\mathbb{Z}_{3}^{2}$. Also,
$C_{8}\leq K$, and in view of (6), we obtain that $|(G_{\\{B\\}})^{*}:K|\leq
2$ and if the index is equal to $2$, then
$(G_{\\{B\\}})^{*}_{u_{0}}\cong(S_{3}\times S_{3})\rtimes\mathbb{Z}_{2}$. A
direct check by Magma [4] shows that in the latter case $(G_{\\{B\\}})^{*}$
has a unique subgroup of index $2$ containing an element of order $8$, which
is also primitive. All these show that $K$ is primitive on $B$.

Denote by $\Delta$ be the subgraph of $\Gamma$ induced by $u_{0}^{E}\cup
u_{1}^{E}$. Using that $E\cong\mathbb{Z}_{2}^{4}$ acting regularly on both
$u_{0}^{E}$ and $u_{1}^{E}$, it is not hard to show that $\Delta$ is the union
of four $3$-dimensional cube $Q_{3}$. If $\Delta_{1}$ is a component of
$\Delta$, then $|V(\Delta_{1})\cap B|=4$ (note that $B=u_{0}^{E}$) and
$V(\Delta_{1})\cap B$ is a block for $K$. This, however, contradicts the fact
that $K$ is primitive on $B$. ∎

We are ready to settle Theorem 5.2, and therefore, Theorem 1.2 as well.

###### Proof of Theorem 5.2..

In view of Lemma 5.3, we may assume that $n>50$. It follows from Lemmas
5.4–5.8 that $G$ admits a normal non-cyclic block system with blocks of size
$4$. Denote this block system by $\mathcal{B}$. Let $K$ be the kernel of the
action of $G$ on $\mathcal{B}$, and for a subgroup $X\leq G$, denote by
$\bar{X}$ the image of $X$ induced by its action on $\mathcal{B}$. As
$\mathcal{B}$ is normal, $\Gamma$ is a normal $r$-cover of
$\Gamma/\mathcal{B}$ for some $r\in\\{1,2,3\\}$. We exclude below all
possibilities case-by-case.

Case 1. $r=1$.

In this case $|K|=4$ and $K\cap C=C_{2}$. If $K\cong\mathbb{Z}_{4}$, then
$C_{2}$ is characteristic in $K$, and therefore, it is normal in $G$. This is
impossible because $\operatorname{core}_{G}(C)=1$, hence
$K\cong\mathbb{Z}_{2}^{2}$

The graph $\Gamma/\mathcal{B}$ is edge-transitive, it has valency $6$, and
$\bar{C}$ is regular on $V(\Gamma/\mathcal{B})$. As $n>50$, Lemma 2.3 can be
applied to $\Gamma/\mathcal{B}$ and $\bar{C}$. It follows that
$\operatorname{Aut}(\Gamma/\mathcal{B})$ has a normal subgroup $N$ such that

  1. (1)

$N=\bar{C}$, or

  2. (2)

$n\equiv 4\\!\\!\pmod{8}$ and $N=\bar{C}_{n/4}$, or

  3. (3)

$N\cong\mathbb{Z}_{3}^{\ell}$ for $\ell\geq 2$ and $\bar{C}_{3}\leq N$.

In case (1), we obtain that $KC\lhd G$, whereas in case (2), $KC_{n/4}\lhd G$.
In either case, $|KC:C|=2$, and therefore, for the derived subgroup
$(KC)^{\prime}$, $(KC)^{\prime}\leq C$. Thus
$(KC)^{\prime}\leq\operatorname{core}_{G}(C)$, and so $(KC)^{\prime}=1$, i.e.,
$KC$ is an abelian group. Then we obtain that $C_{n/2}\lhd G$ in case (1), and
$C_{n/4}\lhd G$ in case (2). None of these is possible because
$\operatorname{core}_{G}(C)=1$.

In case (3), $G$ contains a normal subgroup $M$ such that $KC_{3}\leq M$ and
$M/K\cong\mathbb{Z}_{3}^{\ell^{\prime}}$ for some $\ell^{\prime}\geq 1$. Then
$M$ can be written as $M=KS$ where $C_{3}\leq S$ and
$S\cong\mathbb{Z}_{3}^{\ell^{\prime}}$. As $C_{2}\leq K$, we obtain that
$C_{3}$ commutes with $K$, and so $C_{3}\leq O_{3}(M)$, where $O_{3}(M)$
denotes the largest normal $3$-subgroup of $M$. As $O_{3}(M)$ is
characteristic in $M$, $O_{3}(M)\lhd G$. This yields that
$\operatorname{Orb}(O_{3}(M),V(\Gamma))$ is a non-trivial cyclic block system,
a contradiction to Lemma 5.4.

Case 2. $r=2$.

In this case $\Gamma/\mathcal{B}$ has valency $3$, hence $n\leq 12$ by Lemma
2.2, which is excluded.

Case 3. $r=3$.

The group $K$ is faithful on every block of $\mathcal{B}$. This can be shown
by copying the argument that has been used in Case 3 in the proof of Lemma
5.8. Since $\Gamma/\mathcal{B}$ is a cycle of length $n/2$, it follows that
$|G|\leq|K|\cdot n=24n$. Using that $n>50$, Theorem 2.9 shows that
$\operatorname{core}_{G}(C)\neq 1$, a contradiction. ∎

## References

  * [1] I. Antončič, A. Hujdurović, and K. Kutnar, A classification of pentavalent arc-transitive bicirculants, J. Algebraic. Combin. 41 (2015) 643–668.
  * [2] A. Arroyo, I. Hubard, K. Kutnar, E. O’Reilly, and P. Šparl, Classification of symmetric Tabačjn graphs, Graphs Combin. 31 (2015) 1137–1153.
  * [3] Y.-G. Baik, Y.-Q. Feng, H. S. Sim, and M. Xu, On the normality of Cayley graphs of abelian groups, Algebra Colloq. 5 (1998) 297–304.
  * [4] W. Bosma, C. Cannon, and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput. 24 (1997) 235–265.
  * [5] M. Conder, J.-X. Zhou, Y.-Q. Feng, and M.-M. Zhang, Edge-transitive bi-Cayley graphs, J. Combin. Theory Ser. B 145 (2020) 264–306.
  * [6] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson, Atlas of finite groups, Clarendon Press, Oxford 1985.
  * [7] A. Devillers, M. Giudici, and W. Jein, Arc-transitive bicirculants, J. London Math. Soc. 105 (2022) 1–23.
  * [8] J. D. Dixon and B. Mortimer, Permutation groups, Graduate Text in Mathematics 163, Springer-Verlag, New York 1996.
  * [9] E. Dobson, I. Kovács, and Š. Miklavič, The automorphism groups of non-edge-transitive rose window graphs, Ars. Math. Contemp. 9 (2015) 63–75.
  * [10] R. Frucht, J. E. Graver, and M. E. Watkins, The group of the generalized Petersen graphs, Proc. Camb. Philos. Soc. 70 (1971) 211–218.
  * [11] R. Jajcay, Š. Miklavič, P. Šparl, and G. Vasiljević, On certain edge-transitive bicirculants, Electron. J. Combin. 26 (2) (2019), #P2.6.
  * [12] B. Huppert, Endliche Gruppen I, Springer-Verlag, Berlin Heidelberg New York 1967.
  * [13] I. Kovács, Classifying arc-transitive circulants, J. Algebraic Combin. 20 (2005) 353–358.
  * [14] I. Kovács, Classification of edge-transitive Nest graphs, manuscript.
  * [15] I. Kovács, K. Kutnar, and D. Marušič, Classification of edge-transitive rose window graphs, J. Graph Theory 65 (2010) 216–231.
  * [16] I. Kovács, B. Kuzman, A. Malnič, and S. Wilson, Characterization of edge-transitive $4$-valent bicirculants, J. Graph Theory 69 (2012) 441–463.
  * [17] I. Kovács and J. Ruff, On certain edge-transitive bicirculants of twice odd order, to appear in Electron. J. Combin., preprint arXiv:2111.07982v1 [math.CO], 2021.
  * [18] K. Kutnar, D. Marušič, Š. Miklavič, and R. Strašek, Automorphisms of Tabačjn graphs, Filomat 27 (2013) 1157–1164.
  * [19] C. H. Li, Permutation groups with a cyclic regular subgroup and arc transitive circulants, J. Algebraic Combin. 21 (2005) 131–136.
  * [20] C. H. Li, B. Xia, and S. Zhou, An explicit characterisation of arc-transitive circulants, J. Combin. Theory Ser. B 150 (2021) 1–16.
  * [21] A. Lucchini, On the order of transitive permutation groups with cyclic point-stabiliser, Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. Rend. Lincei (9) Mat. Appl. 9 (1998) 241–243.
  * [22] A. Malnič, D. Marušič, P. Šparl, and B. Frelih, Symmetry structure of bicirculants, Discrete Math. 307 (2007) 409–414.
  * [23] D. Marušič and T. Pisanski, Symmetries of hexagonal molecular graphs on the torus, Croat. Chem. Acta 73 (2000) 969–981.
  * [24] P. Müller, Permutation groups with a cyclic two-orbits subgroup and monodromy groups of Laurent polynomials, Ann. Sc. Norm. Super. Pisa CI Sci. 12 (2013) 369–438.
  * [25] T. Pisanski, A classification of cubic bicirculants, Discrete Math. 307 (2007) 567–578.
  * [26] G. Vasiljević, O simetričnih Nest grafih, MSc thesis, University of Ljubljana, 2017.
  * [27] M. E. Watkins, A Theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory 6 (1969), 152–164.
  * [28] S. Wilson, Rose window graphs, Ars. Math. Contemp. 1 (2008) 7–18.
  * [29] J.-X. Zhou and M.-M. Zhang, The classification of half-arc-regular bi-circulants of valency $6$, European J. Combin. 64 (2017) 45–56.


will stay in the off-shell nilpotent version of the $[Q_{ab}^{(1)}]$ of the
anti-BRST charge. Finally, we have the off-shell nilpotent version of the
anti-BRST charge $[Q_{ab}^{(1)}]$ (derived from the non-nilpotent Noether
conserved anti-BRST charge) as follows

$Q_{ab}\longrightarrow Q_{ab}^{(1)}=\int
d^{D-1}x\,\Big{[}(\partial^{0}\bar{B}^{i}-\partial^{i}\bar{B}^{0})\,\bar{C}_{i}-(\bar{B}^{0}-m\,\bar{B}^{0})\,\bar{C}+(\partial^{0}C^{i}-\partial^{i}C^{0})\,\partial_{i}\bar{\beta}$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-m\,(\dot{C}-m\,C^{0})\,\bar{\beta}+2\,\dot{\lambda}\,\bar{\beta}-\lambda\,\dot{\bar{\beta}}+\rho\,\bar{B}^{0}+(\dot{\bar{C}}-m\,\bar{C}^{0})\,\bar{B}-(\partial^{0}\bar{C}^{i}-\partial^{i}\bar{C}^{0})\,\bar{B}_{i}\Big{]},$
$None$

where, we note that some of the original terms of the Noether conserved anti-
BRST charge $Q_{ab}$ are present which are found to be the anti-BRST invariant
quantities, namely;

$s_{ab}(\lambda\,\dot{\bar{\beta}})=0,\quad s_{ab}(\rho\,\bar{B}^{0}),\quad
s_{ab}[(\dot{\bar{C}}-m\,\bar{C}^{0})\,\bar{B}]=0,\quad
s_{ab}[(\partial^{0}\bar{C}^{i}-\partial^{i}\bar{C}^{0})\,\bar{B}_{i}]=0.$
$None$

It is now straightforward to check that the following is true, namely;

$s_{ab}Q_{ab}^{(1)}=-\,i\,\\{Q_{ab}^{(1)},\,Q_{ab}^{(1)}\\}=0\quad\Longrightarrow\quad[Q_{ab}^{(1)}]^{2}=0,$
$None$

where the l.h.s. can be explicitly computed using the application of the anti-
BRST symmetry transformation $(s_{ab})$ on the explicit expression (A.23).

We end this Appendix with the final remark that, following the theoretical
tricks of our proposal, it is bit involve but straightforward algebra that
leads to the deduction of the off-shell nilpotent ([$Q_{b}^{(1)}]^{2}=0$)
version of the BRST charge [$Q_{b}^{(1)}$] from the non-nilpotent Noether BRST
charge ($Q_{b}$) as follows:

$Q_{b}\longrightarrow Q_{b}^{(1)}=\int
d^{D-1}x\,\Big{[}(\partial^{0}B^{i}-\partial^{i}B^{0})\,C_{i}+(\dot{B}+m\,B^{0})\,C+m\,(\dot{\bar{C}}^{0}-m\,\bar{C}^{0})\,\beta~{}~{}~{}$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\,(\partial^{0}\bar{C}^{i}-\partial^{i}\bar{C}^{0})\,\partial_{i}\beta\,+\,2\,\dot{\rho}\,\beta-\rho\,\dot{\beta}-\lambda\,B^{0}-(\partial^{0}C^{i}-\partial^{i}C^{0})\,B_{i}-(\dot{C}-m\,C^{0})\,B\Big{]}.$
$None$

It is an elementary exercise to check that we have

$s_{b}Q_{b}^{(1)}=-\,i\,\\{Q_{b}^{(1)},\,Q_{b}^{(1)}\\}=0\quad\Longrightarrow\quad[Q_{b}^{(1)}]^{2}=0,$
$None$

where the l.h.s. is computed by an explicit application of $s_{b}$ on the BRST
charge [$Q_{b}^{(1)}$] [cf. Eq. (A.26)] which establishes that we have
obtained the off-shell nilpotent version of the BRST charge [$Q_{b}^{(1)}$]
from the non-nilpotent conserved Noether BRST charge ($Q_{b}$).

## References

  * [1] Becchi, C.; Rouet, A.; Stora, R. The Abelian Higgs Kibble Model, Unitarity of the S-Operator, Phys. Lett. 1974, B52, 344.
  * [2] Becchi, C.; Rouet, A.; Stora, R. Renormalization of the Abelian Higgs-Kibble Model, Commun. Math. Phys. 1975, 42, 127.
  * [3] Becchi, C.; Rouet, A.; Stora, R. Renormalization of Gauge Theories,
Ann. Phys. 1976, 98, 287.

  * [4] Tyutin, I.V. Gauge Invariance in Field Theory and Statistical Physics in Operator Formalism. Lebedev Institute Preprint, Report No.: FIAN-39, arXiv 1975,
arXiv: 0812.0580.

  * [5] Dirac, P. A. M. Lectures on Quantum Mechanics (Belfer Graduate School of Science), Yeshiva University Press, New York (1964).
  * [6] Sundermeyer, K. Constraint Dynamics, Lecture Notes in Physics,
Vol. 169, Springer-Verlag, Berlin (1982).

  * [7] Nishijima, K. BRS invariance, Asymptotic Freedom and Color Confinement
(A Review), Czech. J. Phys. 1996, 46, 1.

  * [8] Henneaux, M.; Teitelboim, C. Quantization of Gauge System,
Princeton University, New Jersey (1992).

  * [9] Nakanishi, N.; Ojima, I. Covariant Operator Formalism of Gauge Theories
and Quantum Gravity, World Scientific: Singapore (1990).

  * [10] Nemschansky, D.; Preitschopf, C.; Weinstein, M.
A BRST Primer, Annals of Physics 1988, 183, 226.

  * [11] Brink, L.; Di Vecchia, P.; Howe, P. A Lagrangian Formulation of the Classical and Quantum Dynamics of Spinning Particles, Nucl. Phys. B 1977, 118, 76.
  * [12] Shukla, A.; Krishna, S.; Malik, R. P. Supersymmetrization of Horizontality Condition: Nilpotent Symmetries for a Free Spinning Relativistic Particle,
Eur. Phy. J. C 2012, 72, 2188.

  * [13] Tripathi, A.; Chauhan, B.; Rao, A. K.; Malik, R. P. Massive Spinning Relativistic Particle: Revisited Under BRST and Supervariable Approaches,
Advances in High Energy Physics 2020, 2020, 1236518 (A Brief Review).

  * [14] Green, M. B.; Schwarz, J. H.; Witten, E. Superstring Theory, Vols. 1 and 2,
Cambridge University Press, Cambridge (1987).

  * [15] Dudal, D.; Lemes, V. E. R.; Sarandy, M. S.; Sorella, S. P.; Picariello, M. On the SL(2, R) symmetry in Yang-Mills Theories in the Landau, Curci-Ferrari and Maximal Abelian Gauge, JHEP 2002, 0212, 008.
  * [16] Dudal, D.; Verschelde, H.; Lemes, V. E. R.; Sarandy, M. S.; Sorella, S. P.; Picariello, M.; Vicini, A.; Gracey, J. A. More on Ghost Condensation in Yang-Mills Theory: BCS Versus Overhauser Effect and the Breakdown of the Nakanishi-Ojima Annex SL(2, R) Symmetry, JHEP 2003, 0306, 003.
  * [17] Gupta, S.; Malik, R. P. A Field-Theoretic Model for Hodge Theory,
Eur. Phy. J. C 2008, 58, 517.

  * [18] Curci, G.; Ferrari, R. Slavnov Transformations and Supersummetry,
Phys. Lett. B 1976, 63, 91.

  * [19] Weinberg, S. The Quantum Theory of Fields, Modern Applications, Vol. 2,
Cambridge University Press, Cambridge (1996).

  * [20] Eguchi, T.; Gilkey, P. B.; Hanson, A. Gravitation, Gauge Theories and Differential Geometry, Phys. Rep. 1980, 66, 213.
  * [21] Mukhi, S.; Mukanda, N. Introduction to Topology, Differential Geometry and Group Theory for Physicists, Wiley Eastern Private Limited, New Delhi (1990).
  * [22] van Holten, J. W. Becchi-Rouet-Stora-Tyutin Cohomology of Compact Gauge Algebras, Phys. Rev. Lett. 1990, 64, 2863.
  * [23] Deser, S.; Gomberoff, A.; Henneaux, M.; Teitelboim, C. Duality, Self-Duality, Sources and Charge Quantization in Abelian N-Form Theories, Phys. Lett. B 1997, 400, 80.
  * [24] Malik, R. P. Abelian 2-Form Gauge Theory: Superfield Formalism,
Eur. Phys. J. C 2009, 60, 457.

  * [25] Rao, A. K.; Malik, R. P. Nilpotent Symmetries of a Modified Massive Abelian 3-Form Theory: Augmented Superfield Approach, Nucl. Phys. B 2022, 983, 115926.
  * [26] Rao, A. K.; Malik, R. P. Modified Massive Abelian 3-Form Theory: Constraint Analysis, Conserved Charges and BRST Algebra, arXiv: 2207.11738 [hep-th].
  * [27] Krishna, S.; Kumar, R.; Malik, R. P. A Massive Field-Theoretic Model for Hodge Theory, Annals of Physics 2020, 414, 168087.
  * [28] Malik, R. P. Gauge Transformations, BRST Cohomology and Wigner’s Little Group, Int. J. Mod. Phys. A 2004, 19, 5663.
  * [29] Malik, R. P. Wigner’s Little Group and BRST Cohomology for One-Form Abelian Gauge Theory, Int. J. Mod. Phys. A 2004, 19, 2721.
  * [30] Malik, R. P. New Topological Field Theories in Two Dimensions,
J. Phys. A: Math Gen. 2001, 34, 4167.

  * [31] Malik, R. P. etal., in preparation.
  * [32] Kumar, R.; Krishna S. Augmented Superfield Approach to Gauge-invariant Massive 2-Form Theory, Eur. Phys. J. C 2017, 77, 387.