# Normal edge-transitive Cayley graphs and
Frattini-like subgroups

1 Behnam Khosravi and 2 Cheryl E. Praeger  1 Department of Mathematics,
Institute for Advanced Studies in Basic Sciences (IASBS), Zanjan 45137-66731,
Iran.
email<EMAIL_ADDRESS>
2 Department of Mathematics and Statistics, The University of Western
Australia, 35 Stirling Highway, Perth, WA 6009, Australia, email
<EMAIL_ADDRESS>
###### Abstract.

For a finite group $G$ and an inverse-closed generating set $C$ of $G$, let
${\rm Aut}(G;C)$ consist of those automorphisms of $G$ which leave $C$
invariant. We define an ${\rm Aut}(G;C)$-invariant normal subgroup $\Phi(G;C)$
of $G$ which has the property that, for any ${\rm Aut}(G;C)$-invariant normal
set of generators for $G$, if we remove from it all the elements of
$\Phi(G;C)$, then the remaining set is still an ${\rm Aut}(G;C)$-invariant
normal generating set for $G$. The subgroup $\Phi(G;C)$ contains the Frattini
subgroup $\Phi(G)$ but the inclusion may be proper. The Cayley graph ${\rm
Cay}(G,C)$ is normal edge-transitive if ${\rm Aut}(G;C)$ acts transitively on
the pairs $\\{c,c^{-1}\\}$ from $C$. We show that, for a normal edge-
transitive Cayley graph ${\rm Cay}(G,C)$, its quotient modulo $\Phi(G;C)$ is
the unique largest normal quotient which is isomorphic to a subdirect product
of normal edge-transitive graphs of characteristically simple groups. In
particular, we may therefore view normal edge-transitive Cayley graphs of
characteristically simple groups as building blocks for normal edge-transitive
Cayley graphs whenever we have $\Phi(G;C)$ trivial. We explore several
questions which these results raise, some concerned with the set of all
inverse-closed generating sets for groups in a given family. In particular we
use this theory to classify all $4$-valent normal edge-transitive Cayley
graphs for dihedral groups; this involves a new construction of an infinite
family of examples, and disproves a conjecture of Talebi.

###### Key words and phrases:

Normal edge-transitive Cayley graphs, Frattini subgroup, graph constructions,
Automorphisms of groups

###### 2000 Mathematics Subject Classification:

Primary: 05C25; Secondary: 08A30; 08A35.

Dedicated to the memory of our colleague and friend Jan Saxl

The second author would like to thank the Isaac Newton Institute for
Mathematical Sciences, Cambridge, for support and hospitality during the
programme _Groups, representations and applications: new perspectives_
(supported by EPSRC grant no. EP/R014604/1), where work on this paper was
undertaken.

##  1\. Introduction and the main results

Let $G$ be a nontrivial finite group (that is, $|G|>1$), and let ${\rm
Aut}(G)$ denote its automorphism group. A non-empty subset $C$ of
$G\setminus\\{1\\}$ is said to be _inverse-closed_ if for each $c\in C$, its
inverse $c^{-1}$ also lies in $C$. We will be concerned with inverse-closed
generating sets $C$ for $G$, and for such a set we let ${\rm Aut}(G;C)$ denote
the subgroup of ${\rm Aut}(G)$ consisting of those automorphisms $\sigma$
which leave $C$ invariant, that is to say, $C^{\sigma}=C$. A subgroup $N\leq
G$ is ${\rm Aut}(G;C)$-invariant if $N^{\sigma}=N$ for each $\sigma\in{\rm
Aut}(G;C)$. We will study

(1) $\mathcal{A}(G;C)=\\{N\mid N\unlhd G,\ N\neq G,\ \mbox{and $N$ is ${\rm
Aut}(G;C)$-invariant}\\}$

and in particular its subset of maximal elements

(2) $\mathcal{A}_{\max}(G;C)=\\{N\in\mathcal{A}(G;C)\mid\ \mbox{$N$ is maximal
by inclusion}\\}.$

Since $|G|>1$, the identity subgroup lies in $\mathcal{A}(G;C)$, and it
follows that $\mathcal{A}_{\max}(G;C)$ is non-empty. Thus the following
subgroup

(3) $\Phi(G;C)=\bigcap\\{N\mid N\in\mathcal{A}_{\max}(G;C)\\}$

is a well defined element of $\mathcal{A}(G;C)$. We may have $\Phi(G;C)=1$;
this is the case, for example, if $G$ is simple so that
$\mathcal{A}_{\max}(G;C)=\mathcal{A}(G;C)=\\{\\{1\\}\\}$. The definition of
$\Phi(G;C)$ as the intersection of a certain family of subgroups of $G$ is
reminiscent of the definition of the Frattini subgroup $\Phi(G)$ as the
intersection of all maximal (proper) subgroups of $G$. Indeed $\Phi(G;C)$
contains $\Phi(G)$ (see Lemma 2.1), but the inclusion can be proper (see
Examples 2.3 and 2.4).

An important property of the Frattini subgroup $\Phi(G)$ is that, if $X$ is a
generating set for $G$ and $X$ contains an element $y\in\Phi(G)$, then
$X\setminus\\{y\\}$ still generates $G$ (see, for example, [7, Satz III.3.2]).
It turns out that $\Phi(G;C)$ has a similar property. We say that a subset $X$
of $G$ is _normal $C$-closed_ if for each $x\in X,g\in G,\sigma\in{\rm
Aut}(G;C)$, the image $(x^{g})^{\sigma}$ also lies in $X$. Clearly an
arbitrary subset $X\subseteq G$ may be enlarged to a normal $C$-closed subset
by adding to it each of the elements $(x^{g})^{\sigma}$; the set thus obtained
is called the _normal $C$-closure_ of $X$. We show that from each normal
$C$-closed generating set we may remove all elements of $\Phi(G;C)$ (if any)
and maintain these properties.

######  Theorem 1.1.

Let $G$ be a finite group and $C$ a generating set for $G$.

  1. (a)

If $X$ is a normal $C$-closed generating set for $G$, then
$X\setminus(X\cap\Phi(G;C))$ is also a normal $C$-closed generating set.

  2. (b)

The subgroup $\Phi(G;C)$ is the set of all elements $y\in G$ which satisfy the
following property:

for $X\subseteq G$, if the normal $C$-closure of $X\cup\\{y\\}$ generates $G$,

then the normal $C$-closure of $X$ also generates $G$.

We will show that this Frattini-like subgroup $\Phi(G;C)$ plays a key role in
describing the structure of normal edge-transitive Cayley graphs.

_We briefly summarise the key concepts:_ for a group $G$, and a non-empty,
inverse-closed subset $C\subseteq G\setminus\\{1\\}$, the (undirected) Cayley
graph ${\rm Cay}(G;C)$ of $G$ with respect to $C$ is the graph with vertex set
$G$ and edge set $E(G;C)$ consisting of all pairs $\\{g,h\\}$ such that
$gh^{-1}\in C$ (or equivalently $hg^{-1}\in C$ since $C$ is inverse-closed).
The graph $\Gamma:={\rm Cay}(G;C)$ is connected if and only if the connection
set $C$ generates $G$. For each $g\in G$, the right multiplication map
$\rho_{g}:h\mapsto hg$ is an automorphism of $\Gamma$, and the group
$G_{R}:=\\{\rho_{g}\mid g\in G\\}$ (called the right regular representation of
$G$) is a subgroup of ${\rm Aut}(\Gamma)$ acting regularly on vertices (that
is, $G_{R}$ is transitive with trivial stabilisers). In addition ${\rm
Aut}(G;C)$ is a subgroup of ${\rm Aut}(\Gamma)$, and the semidirect product
$N(G;C):=G_{R}\rtimes{\rm Aut}(G;C)$ is the full normaliser of $G_{R}$ in
${\rm Aut}(\Gamma)$ (see [6]). As in [11], $\Gamma$ is said to be normal edge-
transitive if $N(G;C)$ is transitive on the edge-set $E(G;C)$. In [11, Theorem
3] it was shown that, for each $N\in\mathcal{A}(G;C)$, the normal quotient,
modulo $N$, of a connected normal edge-transitive Cayley graph ${\rm
Cay}(G;C)$ is again a connected normal edge-transitive Cayley graph, namely
${\rm Cay}(G/N;CN/N)$. In particular if $N\in\mathcal{A}_{\max}(G;C)$, then
the group $G/N$ is characteristically simple, and we refer to ${\rm
Cay}(G/N;CN/N)$ as a _characteristically simple normal quotient_ of ${\rm
Cay}(G;C)$.

We denote the set of connected normal edge-transitive Cayley graphs for finite
characteristically simple groups by ${\sf NormCay{CS}}$. A (still open)
question from [11, Question 2] asks under what conditions ${\rm Cay}(G;C)$ is
determined by its proper normal quotients (that is, quotients modulo subgroups
$N\in\mathcal{A}_{\max}(G;C)$ with $N\neq 1$). Our results suggest that,
provided $\Phi(G;C)=1$, ${\rm Cay}(G;C)$ is determined to a large extent by
its normal quotients lying in ${\sf NormCay{CS}}$. Our main result relies on
certain graph constructions which we define in Subsection 3.1, namely the
direct product $\prod_{i=1}^{n}\Gamma_{i}$ of a family of graphs $\Gamma_{i}$,
and a full subdirect product of a graph direct product. A different graph
theoretical construction was used recently in [8] to study normal edge-
transitive Cayley graphs ${\rm Cay}(G;C)$ of groups $G$ admitting a direct
decomposition $G=M\times N$ with both $M,N\in\mathcal{A}(G;C)$, but the
analysis in [8] does not apply in our general situation.

######  Theorem 1.2.

Let $G$ be a nontrivial finite group with inverse-closed generating set $C$
such that $\Gamma={\rm Cay}(G,C)$ is normal edge-transitive, and let
$\Phi:=\Phi(G;C)$ (as in $\eqref{eq:phi}$). Then there exist $k\geq 1$ and
$N_{1},\dots,N_{k}\in\mathcal{A}_{\max}(G;C)$ for which the following
conditions hold, where $\Gamma_{i}:={\rm Cay}(G/N_{i};CN_{i}/N_{i})$.

  1. (i)

$\Phi=\cap_{i=1}^{k}N_{i}$, and the map
$\zeta:g\Phi\rightarrow(gN_{1},\cdots,gN_{k})$ is an isomorphism
$G/\Phi\rightarrow\prod_{i=1}^{k}G/N_{i}$;

  2. (ii)

for each $i\leq k$, $\Gamma_{i}\in{\sf NormCay{CS}}$,
$\mathcal{A}(G/N_{i};CN_{i}/N_{i})=\\{1\\}$, and $\zeta$ induces a graph
isomorphism from ${\rm Cay}(G/\Phi;C\Phi/\Phi)$ onto a full subdirect product
of $\prod_{i=1}^{k}\Gamma_{i}$.

######  Remark 1.3.

Theorem 1.2 constructs a normal quotient ${\rm
Cay}(G/\Phi(G;C);C\Phi(G;C)/\Phi(G;C))$ of a given normal edge-transitive
Cayley graph ${\rm Cay}(G;C)$ which is a full subdirect product of a family of
its normal quotients lying in ${\sf NormCay{CS}}$. If $\Phi(G;C)=1$ this gives
a structural description of the original graph ${\rm Cay}(G;C)$.

Theorem 1.2 follows fairly easily from a more general result Theorem 3.2 which
considers general normal quotients in ${\sf NormCay{CS}}$. We prove Theorem
1.1 in Section 2, and Theorem 1.2 in Section 3. In Section 4, we work through
this theory for dihedral groups, examining in Theorem 4.1 the possible
structures of inverse-closed generating sets for such groups which are
transitive in the sense of Definition 2.1. By [11, Proposition 1(b)], these
are precisely the connection sets which lead to normal edge-transitive Cayley
graphs. In particular we classify all $4$-valent normal edge-transitive Cayley
graphs for dihedral groups.

######  Theorem 1.4.

Let $G=D_{2n}$ with $n\geq 3$, and let $C$ be an inverse-closed generating set
for $G$ with $|C|=4$. Then ${\rm Cay}(G;C)$ is a $4$-valent normal edge-
transitive Cayley graph if and only if, replacing $C$ by $C^{\sigma}$ for some
$\sigma\in{\rm Aut}(G)$ if necessary, $C$ is as in Example 4.2 or Example 4.5.

The graphs corresponding to subsets $C$ in Example 4.2 were constructed by
Talebi [13], and were conjectured to be the only examples. Our construction in
Example 4.5 contains infinitely many new examples, as demonstrated in
Subsection 4.2.

We note that this and previous work suggests some open questions, and we
mention a few in the next remark.

######  Remark 1.5.

(a) We will see in Section 2 that the ‘relative Frattini subgroups’
$\Phi(G;C)$ may be equal to, or may be much larger than the Frattini subgroup.
They can be soluble or insoluble, even for transitive inverse-closed
generating sets $C$. It is not clear what general properties they may have.
Any additional information would help in understanding the structure of the
corresponding normal edge-transitive Cayley graphs ${\rm Cay}(G;C)$.

(b) Let $C$ be a transitive inverse-closed generating set for a group $G$ in
the sense of Definition 2.1, and suppose that the corresponding normal edge-
transitive Cayley graph ${\rm Cay}(G;C)$ has valency $k$. It follows from
Lemma 2.5 that the normal edge-transitive quotient ${\rm
Cay}(\overline{G};\overline{C})$, where $\overline{G}=G/\Phi(G;C)$ and
$\overline{C}=C\Phi(G;C)/\Phi(G;C)$, has valency $k/\ell$, with $\ell$ as in
Lemma 2.5(b). It is not quite clear what values the parameter $\ell$ can take.
Understanding this better would help in understanding better the structure of
${\rm Cay}(G;C)$.

(c) In Theorem 1.2, we make no claims about the uniqueness of the normal
quotient graphs $\\{\Gamma_{1},\dots,\Gamma_{k}\\}$ in ${\sf NormCay{CS}}$, or
the subgroups $N_{1},\dots,N_{k}\in\mathcal{A}_{\max}(G;C)$. It would be good
to understand this better. In particular, are there examples where these
subgroups and graphs are not uniquely determined by $G,C$?

(d) For dihedral groups $G$, Theorem 4.1 describes the family $\mathcal{T}(G)$
of transitive inverse-closed generating sets $C$, and the corresponding
subgroups ${\rm Aut}(G;C)$ of ${\rm Aut}(G)$. It would be interesting to
explore the set $\mathcal{T}(G)$ for other families of groups, to shed light
on the structure of normal edge-transitive Cayley graphs for these groups. The
sets $\mathcal{T}(G)$ for $G$ a Frobenius group of order $qp$ (with $p$ a
prime) may be extracted from the work of Darafsheh and Assari [4, Section 3]
if $q=4$, and work of Corr and the second author [3] if $q$ is a prime; see
also [1] if $q=3$. Those for nonabelian groups of order $4p^{2}$ ($p$ a prime)
are determined in [10]. Similarly cyclic groups of prime power oprder are
treated in [12], abelian groups of order a power of two primes are treated in
[3], generalised quaternion groups of order $4p$ (with $p$ a prime) in [4,
Section 3], and the $4$-element subsets for certain groups of order $6n$ in
[5]. It would be good to see more general treatments.

##  2\. The Frattini-like subgroup $\Phi(G;C)$

We first prove the assertion that $\Phi(G;C)$ contains the Frattini subgroup.

######  Lemma 2.1.

Let $G$ be a nontrivial finite group with an inverse-closed generating set
$C\subseteq G\setminus\\{1\\}$. Let $\Phi(G;C)$ be as in $\eqref{eq:phi}$, and
let $\Phi(G)$ be the Frattini subgroup. Then

  1. (a)

$\Phi(G)\leq\Phi(G;C)$;

  2. (b)

for $N\in\mathcal{A}_{\max}(G;C)$ and $N\leq M<G$ with $M$ maximal in $G$, we
have $N=\cap_{g\in G,\sigma\in{\rm Aut}(G;C)}(M^{g})^{\sigma}$.

###### Proof.

Let $\mathcal{M}$ be the set of maximal proper subgroups of $G$, so by
definition, $\Phi(G)=\cap_{M\in\mathcal{M}}M$. For each $M\in\mathcal{M}$, and
each $g\in G,\sigma\in{\rm Aut}(G;C)$, the image $(M^{g})^{\sigma}$ is also a
subgroup in $\mathcal{M}$, and so $\Phi(G)\leq N_{M}$, where
$N_{M}:=\cap_{g\in G,\sigma\in{\rm Aut}(G;C)}(M^{g})^{\sigma}$. Note that, by
definition, $N_{M}\in\mathcal{A}(G;C)$.

Now let $N\in\mathcal{A}_{\max}(G;C)$, and let $M\in\mathcal{M}$ such that
$N\leq M$ (note that such an $M$ exists since $G$ is finite). Then $N\leq
N_{M}$ since $N$ is normal in $G$ and ${\rm Aut}(G;C)$-invariant. By the
maximality of $N$, it now follows that $N=N_{M}$, proving part (b). Since this
holds for all $N\in\mathcal{A}_{\max}(G;C)$, it follows that
$\Phi(G)\leq\cap_{N\in\mathcal{A}_{\max}(G;C)}N=\Phi(G;C)$, proving part (a).
∎

Sometimes equality holds in Lemma 2.1(a), for example when $G$ is a cyclic
group (Example 2.2). It is also easy to construct examples for which equality
does not hold, for example, when $G$ is a dihedral group (Example 2.3), or is
almost simple but not simple (Example 2.4). Example 2.3 shows how $\Phi(G;C)$
can vary for different inverse-closed generating sets $C$.

######  Example 2.2.

Let $G=\langle a\mid a^{n}=1\rangle\cong Z_{n}$ with $n\geq 2$. Each subgroup
of $G$ is normal and ${\rm Aut}(G)$-invariant. In particular the maximal
subgroups of $G$ are the cyclic subgroups $M_{p}=\langle a^{p}\rangle\cong
Z_{n/p}$, for primes $p$ dividing $n$. These are also the maximal normal ${\rm
Aut}(G;C)$-invariant subgroups for each inverse-closed generating set $C$ of
$G$. Thus the Frattini subgroup (which is the intersection of all the maximal
subgroups of $G$), and also $\Phi(G;C)$, are equal to

$\Phi(G)=\Phi(G;C)=\langle a^{m}\rangle,\ \mbox{where $m$ is the product of
the distinct prime divisors of $n$.}$

In particular, $\Phi(G)=\Phi(G;C)=1$ if and only if $n$ is square-free.

The next example is for the dihedral group

(4) $G=\langle a,b\mid a^{n}=b^{2}=1,bab=a^{-1}\rangle\cong D_{2n}$

of order $2n$. This group $G$ admits automorphisms $\varphi,\tau_{k}$, for
positive integers $k<n$ such that $\gcd(k,n)=1$, defined on the generators
$a,b$ as follows:

(5) $\varphi:a\to a,\ b\to ba;\quad\tau_{k}:a\to a^{k},\ b\to b,$

and we have

(6) ${\rm Aut}(G)=A\rtimes T,\ \mbox{where}\ A=\langle\varphi\rangle\cong
Z_{n},\ \mbox{and}\ T=\\{\tau_{k}\mid 1\leq k\leq n-1,\
\gcd(k,n)=1\\}\cong{\rm Aut}(Z_{n}).$

######  Example 2.3.

Let $G\cong D_{2n}$, as in (4), with $n\geq 3$. If $n$ is odd then the $n$
involutions in $G$ form a single $G$-conjugacy class. On the other hand, if
$n$ is even then the $n$ non-central involutions form two $G$-conjugacy
classes of size $n/2$, with representatives $b,ba$, and $\varphi\in{\rm
Aut}(G)$ interchanges these two classes.

The maximal subgroups of $G$ are of two types. Firstly there is the cyclic
subgroup $M=\langle a\rangle\cong Z_{n}$. Secondly, for each prime $p$
dividing $n$, we have a dihedral subgroup

$M_{p}:=\langle a^{p},b\rangle\cong D_{2n/p}\ \mbox{and also, if $n$ is even
and $p=2$,}\ M_{2}^{\prime}:=\langle a^{2},ba\rangle\cong D_{n}.$

If $n$ is even then the two subgroups $M_{2},M_{2}^{\prime}$ are distinct
index $2$ (hence normal) subgroups of $G$, and $M_{2}\cap
M_{2}^{\prime}=\langle a^{2}\rangle$. Thus, for arbitrary $n$, the Frattini
subgroup (which is the intersection of all the maximal subgroups of $G$) is
equal to

$\Phi(G)=\langle a^{m}\rangle,\ \mbox{where $m$ is the product of the distinct
prime divisors of $n$.}$

For example, $\Phi(G)=1$ if and only if $n$ is square-free. Now we consider
$\Phi(G;C)$ for two particular inverse-closed generating sets $C$ of $G$,
namely

$C_{1}=\\{a,a^{-1},b\\},\quad\mbox{and}\quad C_{2}=\\{b,ba\\}.$

In each case, to determine $\Phi(G;C)$ we first identify ${\rm Aut}(G;C)$, and
then we find all subgroups $N\in\mathcal{A}_{\max}(G;C)$, that is to say, all
proper normal subgroups $N$ of $G$ which are maximal subject to being ${\rm
Aut}(G;C)$-invariant. It follows from (6) and the definitions of the $C_{i}$
that ${\rm Aut}(G;C_{1})=\langle\tau_{n-1}\rangle\cong Z_{2}$, and ${\rm
Aut}(G;C_{2})=\langle\tau_{n-1}\varphi\rangle\cong Z_{2}$. In both cases the
subgroup $M=\langle a\rangle$ is invariant under ${\rm Aut}(G)$, and hence
$M\in\mathcal{A}_{\max}(G;C_{i})$ so $\Phi(G;C_{i})\leq M$ for each $i$. Let
$N$ be an arbitrary subgroup in $\mathcal{A}_{\max}(G;C_{i})$. Since $N$ is a
proper subgroup of $G$ it is contained in some maximal subgroup, namely either
$M$, or one if the $M_{p}$ or $M_{2}^{\prime}$ (with $n$ even in the last
case). If $N\leq M$, then by maximality $N=M$. If $N\leq M_{p}$ for some odd
prime $p$, then, as $N$ is normal in $G$, it follows that $N$ is contained in
$\cap_{g\in G}M_{p}^{g}=\langle a^{p}\rangle$, and hence $N$ is a proper
subgroup of $M$, contradicting the maximality of $N$. Thus

$\mbox{if $n$ is odd then, for each $i$,
$\mathcal{A}_{\max}(G;C_{i})=\\{\langle a\rangle\\}$ and
$\Phi(G;C_{i})=\langle a\rangle>\Phi(G)$}.$

Suppose now that $n$ is even. We showed above that either $N=M$ or $N\leq
M_{2}$ or $N\leq M_{2}^{\prime}$. If $i=1$ then each of $M_{2},M_{2}^{\prime}$
is left invariant by ${\rm Aut}(G;C_{1})=\langle\tau_{n-1}\rangle$ and so

$\mbox{if $n$ is even then $\mathcal{A}_{\max}(G;C_{1})=\\{\langle
a\rangle,M_{2},M_{2}^{\prime}\\}$ and hence $\Phi(G;C_{1})=\langle
a^{2}\rangle\geq\Phi(G)$},$

and in fact $\Phi(G)<\Phi(G;C_{1})$ unless $n=2^{e}\geq 4$, in which case
$\Phi(G;C_{1})=\Phi(G)=\langle a^{2}\rangle>1$. If $i=2$ and $N$ is contained
in one of $M_{2},M_{2}^{\prime}$, then since ${\rm
Aut}(G;C_{2})=\langle\tau_{n-1}\varphi\rangle$ interchanges $M_{2}$ and
$M_{2}^{\prime}$, we have $N\leq M_{2}\cap M_{2}^{\prime}=\langle
a^{2}\rangle<M$, contradicting the maximality of $N$. Thus

$\mbox{if $n$ is even then $\mathcal{A}_{\max}(G;C_{2})=\\{\langle
a\rangle\\}$ and $\Phi(G;C_{2})=\langle a\rangle>\Phi(G)$}.$

######  Example 2.4.

Let $G$ be an almost simple group with unique minimal normal subgroup $T$, a
nonabelian simple group. If $G=T$, then the only proper normal subgroup of $G$
is the trivial subgroup and hence $\Phi(G)=\Phi(G;C)=1$ for all inverse-closed
generating sets $C$.

Suppose now that $G\neq T$. For example $(G,T)=(S_{5},A_{5})$. Then $G$ has a
maximal proper subgroup $M$ which does not contain $T$. (This assertion
follows from the finite simple group classification.) Thus
$\Phi(G)\leq\cap_{g\in G}M^{g}=1$, that is, $\Phi(G)=1$. On the other hand,
each maximal proper normal subgroup $N$ contains $T$, and for any generating
set $C$ for $G$, the subgroup $T$ is ${\rm Aut}(G;C)$-invariant. Thus
$\Phi(G;C)\geq T$ and so $\Phi(G;C)>\Phi(G)$. Often we will have
$\mathcal{A}_{\max}(G;C)=\\{T\\}$ so that $\Phi(G;C)=T$, but this is not
necessarily the case. For example if $G={\rm P}\Gamma{\rm L}(2,2^{p^{2}})$
with $T={\rm PSL}(2,2^{p^{2}})$, for some odd prime $p$, then
$\mathcal{A}_{\max}(G;C)=\\{T.p\\}$ and $\Phi(G;C)=T.p$.

We now prove Theorem 1.1.

###### Proof.

_of Theorem_ 1.1. Let $G=\langle C\rangle$.
(a) Let $X$ be a normal $C$-closed generating set of $G$, and let
$Y=X\setminus(X\cap\Phi(G;C))$. By (3), $\Phi(G;C)$ is normal $C$-closed, and
hence also $Y$ is normal $C$-closed. This implies that $K:=\langle Y\rangle$
is a normal ${\rm Aut}(G;C)$-invariant subgroup of $G$. Suppose that $K\neq
G$. Then $K\in\mathcal{A}(G;C)$, and there exists
$N\in\mathcal{A}_{\max}(G;C)$ such that $K\leq N$. By definition $Y\subseteq
K\subseteq N$, and also $X\cap\Phi(G;C)\subseteq\Phi(G;C)\subseteq N$ by (3).
Thus $X\subseteq N$, which is a contradiction since $X$ generates $G$. Thus
$K=G$, and hence $Y$ is a normal $C$-closed generating set.

(b) Let $S$ be the subset consisting of all elements $y$ of $G$ which satisfy
the condition in Theorem 1.1(b). Then by part (a), $\Phi(G;C)\subseteq S$. Now
let $y\in S$ and let $N\in\mathcal{A}_{\max}(G;C)$. We claim that $y\in N$.
Suppose to the contrary that $y\not\in N$. Let
$\widehat{N}=N\cup\\{(y^{g})^{\sigma}\mid\sigma\in{\rm Aut}(G;C),g\in G\\}$
(the normal $C$-closure of $N\cup\\{y\\}$), and let
$M=\langle\widehat{N}\rangle$. Since $N$ is normal in $G$ and ${\rm
Aut}(G;C)$-invariant, the subgroup $M$ is also normal in $G$ and ${\rm
Aut}(G;C)$-invariant. Then since $N$ is properly contained in $M$ and
$N\in\mathcal{A}_{\max}(G;C)$, it follows that $G=M$. Then, since $y$
satisfies the condition in Theorem 1.1(b), the normal $C$-closure of $N$
(which is just $N$ itself) must generate $G$. This is a contradiction. Hence
$y\in N$. Since this holds for all $N\in\mathcal{A}_{\max}(G;C)$ it follows
from (3) that $y\in\Phi(G;C)$. ∎

###  2.1. Transitive inverse-closed generating sets

For our application to normal edge-transitive Cayley graphs, we are interested
in generating sets $C$ for $G$ which have the following property (see [11,
Lemma 1]).

######  Definition 2.1.

An inverse-closed generating set $C$ for a nontrivial group $G$ is said to be
_transitive_ if either the ${\rm Aut}(G;C)$-action on $C$ is transitive, or
there are two orbits $C_{+}$ and $C_{-}$ in this action such that $C=C_{+}\cup
C_{-}$ and $C_{-}=(C_{+})^{-1}$, where $(C_{+})^{-1}=\\{c^{-1}\mid c\in
C_{+}\\}$.

Transitive generating sets have some useful properties.

######  Lemma 2.5.

Let $G$ be a nontrivial finite group with transitive inverse-closed generating
set $C$. Then

  1. (a)

$C\cap\Phi(G;C)=\emptyset$;

  2. (b)

there is a positive integer $\ell$ such that $|C\cap
y\Phi(G;C)|\in\\{0,\ell\\}$ for each $y\in G$. Moreover, if both $C\cap
y\Phi(G;C)\neq\emptyset$ and $C\cap y^{\prime}\Phi(G;C)\neq\emptyset$, then
there exists $\sigma\in{\rm Aut}(G;C)$ such that
$(y^{\prime}\Phi(G;C))^{\sigma}$ is either $y\Phi(G;C)$ or $y^{-1}\Phi(G;C)$.

###### Proof.

(a) Suppose that $c\in C\cap\Phi(G;C)$. Then, since $\Phi(G;C)$ is ${\rm
Aut}(G;C)$-invariant, each element of the orbit containing $c$, under the
natural action of ${\rm Aut}(G;C)$, lies in $\Phi(G;C)$. By Definition 2.1,
this means that for each $c^{\prime}\in C$, either $c^{\prime}$ or its inverse
lies in $\Phi(G;C)$. Then since $\Phi(G;C)$ is closed under forming inverses
(as it is a subgroup), we have $C\subseteq\Phi(G;C)$. Hence $G=\langle
C\rangle\leq\Phi(G;C)$, which is a contradiction, since $\Phi(G;C)$ is a
proper subgroup.

(b) Suppose that $C\cap y\Phi(G;C)\neq\emptyset$ and $C\cap
y^{\prime}\Phi(G;C)\neq\emptyset$. Then there exist $c,c^{\prime}\in C$ such
that $y\Phi(G;C)=c\Phi(G;C)$ and $y^{\prime}\Phi(G;C)=c^{\prime}\Phi(G;C)$. By
Definition 2.1, there exists $\sigma\in{\rm Aut}(G;C)$ such that
$(c^{\prime})^{\sigma}$ is equal to either $c$ or $c^{-1}$, and hence, since
$\Phi(G;C)$ is ${\rm Aut}(G;C)$-invariant,
$(y^{\prime}\Phi(G;C))^{\sigma}=(c^{\prime}\Phi(G;C))^{\sigma}$ is either
$c\Phi(G;C)=y\Phi(G;C)$ or $c^{-1}\Phi(G;C)=y^{-1}\Phi(G;C)$. Note that, since
$\Phi(G;C)$ is a normal subgroup of $G$, we have
$(c\Phi(G;C))^{-1}=c^{-1}\Phi(G;C)$. Then, since $C$ is inverse-closed,
$(C\cap c\Phi(G;C))^{-1}=C^{-1}\cap(c\Phi(G;C))^{-1}=C\cap c^{-1}\Phi(G;C)$.
Thus, the cardinality $|C\cap y^{\prime}\Phi(G;C)|=|C\cap y\Phi(G;C)|$ is
constant for all non-empty intersections. ∎

##  3\. Quotients of normal edge-transitive graphs

In this section we prove Theorem 1.2, as a consequence of a more general
result, Theorem 3.2. First we summarise our notation for graphs and their
homomorphisms.

###  3.1. Graph concepts

We will only consider finite simple undirected graphs. That is, a _graph_
$\Gamma=(V,E)$ will consist of a finite set $V$ of vertices, and a set $E$ of
edges, where each edge is an unordered pair of distinct vertices. We often
denote the vertex set and the edge set of $\Gamma$ by $V(\Gamma)$ and
$E(\Gamma)$, respectively.

A _subgraph_ $\Gamma^{\prime}=(V^{\prime},E^{\prime})$ of $\Gamma=(V,E)$, is a
graph with $V^{\prime}\subseteq V$, $E^{\prime}\subseteq E$, and each
$\\{u,v\\}\in E^{\prime}$ is a subset of $V^{\prime}$. A _homomorphism_ from
$\Gamma_{1}=(V_{1},E_{1})$ to $\Gamma_{2}=(V_{2},E_{2})$ is a map $f:V_{1}\to
V_{2}$ such that, for each $\\{u,v\\}\in E_{1}$, the image
$\\{u^{f},v^{f}\\}\in E_{2}$. A graph homomorphism $f$ is called

  * •

an epimorphism, if $f$ is onto (on vertices);

  * •

a full homomorphism, if the induced map $E_{1}\to E_{2}$ is onto;

  * •

a full epimorphism, if $f$ is both an epimorphism and a full homomorphism;

  * •

an isomorphism if $f$ is a full homomorphism and is a bijection on vertices;
in this case $\Gamma_{1}$ and $\Gamma_{2}$ are said to be _isomorphic_ ,
written $\Gamma_{1}\cong\Gamma_{2}$.

For graphs $\Gamma_{i}=(V_{i},E_{i})$, where $1\leq i\leq n$, their _direct
product_ is the graph $(V,E)$ with $V=V_{1}\times\dots\times V_{n}$ and $E$
consisting of all the pairs $\\{u,v\\}\subset V$ such that
$\\{u_{i},v_{i}\\}\in E_{i}$ for each $i\leq n$. We denote this graph by
$\prod_{i=1}^{n}\Gamma_{i}$. A _subdirect product_ of a family of graphs
$\\{\Gamma_{1},\dots,\Gamma_{n}\\}$ is a subgraph $\Gamma$ of the direct
product $\prod_{i=1}^{n}\Gamma_{i}$ such that, for each $i\leq n$, the natural
map $\pi_{i}:\Gamma\to\Gamma_{i}$ (where $\pi_{i}:u\to u_{i}$) is a graph
epimorphism. It is called a full subdirect product if each $\pi_{i}$ is a full
epimorphism (see [2]).

Our main graph theoretical result Theorem 1.2 relies in an essential way on
the following fact about products of Cayley graphs.

######  Lemma 3.1.

Let $n$ be a positive integer $n\geq 2$, and let $G_{1},\dots,G_{n}$ be
nontrivial finite groups with inverse-closed generating sets
$C_{1},\dots,C_{n}$, respectively. Consider the Cayley graphs

$\Gamma:={\rm Cay}(G_{1}\times\dots\times G_{n},C_{1}\times\dots\times
C_{n}),\ \text{and}\ \Gamma_{i}:={\rm Cay}(G_{i},C_{i}),\ \text{for}\
i=1,\dots,n.$

Then $\Gamma$ is the direct product graph $\prod_{i=1}^{n}\Gamma_{i}$.

###### Proof.

By the definition of a Cayley graph, for each $i$, the edge set of
$\Gamma_{i}$ is the set of all pairs of the form $\\{g_{i},c_{i}g_{i}\\}$ with
$g_{i}\in G_{i}$ and $c_{i}\in C_{i}$. Similarly, the edge-set of $\Gamma$ is
the set of all pairs of the form $\\{g,cg\\}$ where
$g=(g_{1},\dots,g_{n})\in\prod_{i=1}^{n}G_{i}$ and
$c=(c_{1},\dots,c_{n})\in\prod_{i=1}^{n}C_{i}$. In such a pair the element
$cg=(c_{1}g_{1},\dots,c_{n}g_{n})$, and hence these pairs $\\{g,cg\\}$ are
precisely the pairs for which $\\{g_{i},c_{i}g_{i}\\}$ is an edge of
$\Gamma_{i}$, for each $i=1,\dots,n$. By the definition of a direct product
graph, $\Gamma$ is the direct product $\prod_{i=1}^{n}\Gamma_{i}$. ∎

###  3.2. Proof of Theorem 1.2

Now we state and prove our main decomposition result for normal edge-
transitive Cayley graphs. Recall that, for an inverse-closed generating set
$C$ for a group $G$, ${\rm Cay}(G;C)$ is normal edge-transitive if and only if
$G_{R}\rtimes{\rm Aut}(G;C)$ is transitive on edges and, by [11, Proposition
1(b)], this is equivalent to the set $C$ being transitive in the sense of
Definition 2.1.

######  Theorem 3.2.

Let $G$ be a nontrivial finite group with inverse-closed generating set $C$
such that $\Gamma={\rm Cay}(G;C)$ is normal edge-transitive. Then there exist
$k\geq 1$ and $N_{1},\dots,N_{k}\in\mathcal{A}_{\max}(G;C)$ for which the
following conditions hold for the subgroup $X:=\cap_{i=1}^{k}N_{i}$ and
quotient graphs $\Gamma_{i}:={\rm Cay}(G/N_{i};CN_{i}/N_{i})$.

  1. (i)

$X\in\mathcal{A}(G;C)$ and the map $\zeta:gX\rightarrow(gN_{1},\cdots,gN_{k})$
is a group isomorphism $G/X\rightarrow\prod_{i=1}^{k}G/N_{i}$;

  2. (ii)

for each $i\leq k$, $\Gamma_{i}\in{\sf NormCay{CS}}$, and $\zeta$ induces a
graph isomorphism from ${\rm Cay}(G/X;CX/X)$ onto a full subdirect product of
$\prod_{i=1}^{k}\Gamma_{i}$.

  3. (iii)

Moreover the unique smallest $X$ for which both (i) and (ii) hold is
$X=\Phi(G;C)$.

###### Proof.

We prove parts (i) and (ii) by induction on $|G|$. These assertions hold if
$\mathcal{A}_{\max}(G;C)=\\{\\{1_{G}\\}\\}$, since in this case $G$ is
characteristically simple and so ${\rm Cay}(G;C)\in{\sf NormCay{CS}}$, and we
take $k=1$ and $X=N_{1}=\Phi(G;C)=1$. In particular this is the case if $G$ is
simple. Suppose inductively that $\mathcal{A}_{\max}(G;C)$ consists of
nontrivial subgroups, and that parts (i) and (ii) hold for groups of order
less than $|G|$.

Choose $N_{1}\in\mathcal{A}_{\max}(G;C)$. By definition $G/N_{1}$ is
characteristically simple and since the graph $\Gamma_{1}:={\rm
Cay}(G/N_{1};CN_{1}/N_{1})$ is normal edge-transitive by [11, Theorem 3(c)],
we have $\Gamma_{1}\in{\sf NormCay{CS}}$. Let $H\in\mathcal{A}(G;C)$ and
suppose that $N_{1}H\neq G$. Then $N_{1}H$ is a proper normal subgroup of $G$
and is ${\rm Aut}(G;C)$-invariant, and hence $N_{1}H\in\mathcal{A}(G;C)$. By
the maximality of $N_{1}$, it follows that $N_{1}H=N_{1}$, that is to say,
$H\leq N_{1}$. If this is true for all $H\in\mathcal{A}(G;C)$, then $N_{1}$ is
the unique maximal element of $\mathcal{A}(G;C)$, and hence
$\mathcal{A}_{\max}(G;C)=\\{N_{1}\\}$, $\Phi(G;C)=N_{1}$, and parts (i) and
(ii) hold with $k=1,X=\Phi(G;C)=N_{1}$.

Thus we may assume that there exists $H\in\mathcal{A}(G;C)$ such that
$N_{1}H=G$. Since $N_{1}\neq G$, we have $H\neq 1$ so $|G/H|<|G|$, and by
induction parts (i) and (ii) hold for $G/H$ with generating set $CH/H$. Hence
there exists $k\geq 2$ and subgroups
$\overline{N}_{2},\dots,\overline{N}_{k}\in\mathcal{A}_{\max}(G/H;CH/H)$ such
that parts (i)–(ii) hold with

$\overline{G}=G/H,\ \overline{C}=CH/H,\ k-1,\ \overline{N}_{i},\
\overline{K}=\cap_{i=2}^{k}\overline{N}_{i},\ \overline{\Gamma}_{i}={\rm
Cay}(\overline{G}/\overline{N}_{i};\overline{C}\overline{N}_{i}/\overline{N}_{i}),$

and
$\overline{\zeta}:\overline{G}/\overline{K}\rightarrow\prod_{i=2}^{k}\overline{G}/\overline{N}_{i}$
in place of $G,C,k,N_{i},X,\Gamma_{i},\zeta$, respectively. By induction,
$\overline{\zeta}$ induces a graph isomorphism from ${\rm
Cay}(\overline{G}/\overline{K};\overline{C}\overline{K}/\overline{K})$ onto a
full subdirect product of $\prod_{i=2}^{k}\overline{\Gamma}_{i}$. Note that
each $\overline{N}_{i}$ is of the form $N_{i}/H$ for a unique
$N_{i}\in\mathcal{A}_{\max}(G;C)$ such that $H\leq N_{i}$. Moreover,
$\overline{G}/\overline{N_{i}}\cong G/N_{i}$ and the natural map
$\nu_{i}:xN_{i}\to\overline{x}\overline{N}_{i}$, where
$\overline{x}=xH\in\overline{G}=G/H$, defines an isomorphism
$G/N_{i}\to\overline{G}/\overline{N_{i}}$. If $x\in CN_{i}$, then
$\overline{x}=xH\in(CN_{i})/H=\overline{CN_{i}}$, and hence
$(CN_{i}/N_{i})\nu_{i}=\overline{CN_{i}}/\overline{N_{i}}$. It follows that
$\nu_{i}$ induces a graph isomorphism from $\Gamma_{i}:={\rm
Cay}(G/N_{i},CN_{i}/N_{i})$ to $\overline{\Gamma}_{i}$. In particular
$\Gamma_{i}\in{\sf NormCay{CS}}$ for $2\leq i\leq k$. Moreover the map

$\nu:(\overline{x}_{2}\overline{N}_{2},\dots,\overline{x}_{k}\overline{N}_{k})\to(\overline{x}_{2}\overline{N}_{2}\nu_{2}^{-1},\dots,\overline{x}_{k}\overline{N}_{k}\nu_{k}^{-1})=(x_{2}N_{2},\dots,x_{k}N_{k})$

is a group isomorphism
$\nu:\prod_{i=2}^{k}\overline{G}/\overline{N}_{i}\to\prod_{i=2}^{k}G/N_{i}$.
Setting $K:=\cap_{i=2}^{k}N_{i}$, we have
$\overline{K}=K/H\in\mathcal{A}(\overline{G};\overline{C})$ and
$K\in\mathcal{A}(G;C)$, and a natural isomorphism
$\mu:G/K\to\overline{G}/\overline{K}$ given by
$\mu:xK\to\overline{x}\overline{K}$. The composition
$\zeta^{\prime}:=\mu\circ\overline{\zeta}\circ\nu$ is a group homomorphism
$\zeta^{\prime}:G/K\to\prod_{i=2}^{k}G/N_{i}$ such that
$\zeta^{\prime}:xK\rightarrow(xN_{2},\dots,xN_{k})$ for each $x\in G$.

_Proof of part (i)._ Let $X:=\cap_{i=1}^{k}N_{i}=N_{1}\cap K$. Then since each
$N_{i}\in\mathcal{A}_{\max}(G;C)$ we have $X\in\mathcal{A}(G;C)$. Also since
$G=N_{1}H$ and $H\leq K$, we have $G=N_{1}K$. The quotient $G/X$ has normal
subgroups $K/X$ and $N_{1}/X$ that intersect trivially, and hence $G/X\cong
K/X\times N_{1}/X$. Since also $K/X\cong KN_{1}/N_{1}=G/N_{1}$ and
$N_{1}/X\cong N_{1}K/K=G/K$, it follows that the map
$\zeta_{1}:xX\rightarrow(xN_{1},xK)$ is an isomorphism from $G/X$ to
$G/N_{1}\times G/K$. Now the map $\zeta_{2}:G/N_{1}\times
G/K\to\prod_{i=1}^{k}G/N_{i}$ given by
$(xN_{1},xK)\zeta_{2}=(xN_{1},(xK)\zeta^{\prime})$ is also an isomorphism, and
therefore the composition
$\zeta:=\zeta_{1}\circ\zeta_{2}:G/X\rightarrow\prod_{i=1}^{k}G/N_{i}$ is the
natural isomorphism required in part (i).

_Proof of part (ii)._ We have seen already that each $\Gamma_{i}\in{\sf
NormCay{CS}}$. Now we prove the rest of part (ii). The map $\zeta$ induces a
graph isomorphism from $\Sigma:={\rm Cay}(G/X,CX/X)$ to ${\rm
Cay}(\prod_{i=1}^{k}G/N_{i},(CX/X)\zeta)$. To determine $(CX/X)\zeta$, note
that, since $X=\cap_{i=1}^{k}N_{i}$ is contained in each $N_{i}$, for each
$c\in C$ and $x\in X$ the image $(cxX)\zeta=(cN_{1},\dots,cN_{k})$, and thus
$(CX/X)\zeta\subseteq\prod_{i=1}^{k}CN_{i}/N_{i}$. Hence $\Sigma\zeta$ is a
subgraph of ${\rm Cay}(\prod_{i=1}^{k}G/N_{i},\prod_{i=1}^{k}CN_{i}/N_{i})$
which, by Lemma 3.1, is isomorphic to the direct product graph
$\prod_{i=1}^{k}{\rm Cay}(G/N_{i},CN_{i}/N_{i})=\prod_{i=1}^{k}\Gamma_{i}$.
Moreover it follows from the definition of $\Sigma$ that the image of
$\Sigma\zeta$ under the $j^{th}$ projection map
$\pi_{j}:\prod_{i=1}^{k}\Gamma_{i}\rightarrow\Gamma_{j}$ is equal to
$\Gamma_{j}$ so $\Sigma\zeta$ is a subdirect product of
$\prod_{i=1}^{k}\Gamma_{i}$. Finally each edge of $\Gamma_{j}$ is of the form
$e=\\{gN_{j},cgN_{j}\\}$ for some $c\in C$, $g\in G$, and so $e$ is the image
under $\zeta\pi_{j}$ of the edge $\\{gX,cgX\\}$ of $\Sigma$. Thus
$\Sigma\zeta$ is a full subdirect product and part (ii) holds.

Therefore parts (i) and (ii) have been proved by induction. It remains to
prove part (iii).

Proof of part (iii). From all the sets of subgroups
$N_{1},\dots,N_{k}\in\mathcal{A}_{\max}(G;C)$ such that parts (i) and (ii)
hold with $X=\cap_{i=1}^{k}N_{i}$ and
$\zeta:gX\rightarrow(gN_{1},\dots,gN_{k})$ and the $\Gamma_{i}={\rm
Cay}(G/N_{i},CN_{i}/N_{i})\in{\sf NormCay{CS}}$, choose the subgroups
$N_{1},\dots,N_{k}$ such that $|X|$ is as small as possible. We claim that
$X=\Phi(G;C)$. Note that, by the definitions of $\Phi(G;C)$ and $X$, it
follows that $X\in\mathcal{A}(G;C)$ and $\Phi(G;C)\leq X$. To prove the claim
it is therefore sufficient to show that each $N\in\mathcal{A}_{\max}(G;C)$
contains $X$, since this will imply that $\Phi(G;C)\geq X$ and hence
$\Phi(G;C)=X$.

Suppose to the contrary that there exists $N\in\mathcal{A}_{\max}(G;C)$ such
that $X\not\leq N$. Then $NX$ properly contains $N$ and by the maximality of
$N$, we have $G=NX$. Let $Y=N\cap X$. Then the same argument as in the proof
of part (i) shows that $G/Y\cong N/Y\times X/Y\cong G/X\times G/N$, and that
the map $\zeta_{1}:gY\rightarrow(gX,gN)$ is an isomorphism from $G/Y$ to
$G/X\times G/N$; and further, that the composition of $\zeta_{1}$ followed by
the map $(gX,gN)\rightarrow((gX)\zeta,gN)$ from $G/X\times G/N$ to
$(\prod_{i=1}^{k}G/N_{i})\times G/N$ is the natural isomorphism
$\zeta^{\prime}$ from $G/Y$ to $\prod_{i=1}^{k+1}G/N_{i}$, where $N_{k+1}:=N$.
Note that $\Gamma_{k+1}:={\rm Cay}(G/N_{k+1},CN_{k+1}/N_{k+1})\in{\sf
NormCay{CS}}$ since $N\in\mathcal{A}_{\max}(G;C)$. Then the argument in the
proof of part (ii) shows that $\zeta^{\prime}$ induces an isomorphism from
${\rm Cay}(G/Y,CY/Y)$ onto a full subdirect product of
$\prod_{i=1}^{k+1}\Gamma_{i}$. Thus parts (i) and (ii) hold for
$N_{1},\dots,N_{k+1}\in\mathcal{A}_{\max}(G;C)$, and we have
$Y=\cap_{i=1}^{k+1}N_{i}=X\cap N_{k+1}$, a proper subgroup of $X$. This
contradicts the minimality of $|X|$. Hence each $N\in\mathcal{A}_{\max}(G;C)$
contains $X$, and therefore $X=\Phi(G;C)$. ∎

Finally in this subsection we prove Theorem 1.2.

###### Proof.

_of Theorem_ 1.2. By Theorem 3.2(iii), for the group $X=\Phi(G;C)$, parts (i)
and (ii) of Theorem 3.2 hold. This yields everything we need for Theorem 1.2
except for the assertion that
$\mathcal{A}(G/N_{i},CN_{i}/N_{i})=\\{\\{1\\}\\}$ for each $i$. To prove this
last assertion, recall that each of the subgroups
$N_{i}\in\mathcal{A}_{\max}(G;C)$. Suppose to the contrary that, for some $i$,
there exists a nontrivial $M_{i}\in\mathcal{A}(G/N_{i},CN_{i}/N_{i})$. Then
$M_{i}=M/N_{i}$ where $M\unlhd G$, $N_{i}<M<G$, and $M/N_{i}$ is invariant
under ${\rm Aut}(G/N_{i};CN_{i}/N_{i})$. In particular $M/N_{i}$ is invariant
under the subgroup of ${\rm Aut}(G/N_{i};CN_{i}/N_{i})$ induced by the action
of ${\rm Aut}(G;C)$, and hence $M$ is ${\rm Aut}(G;C)$-invariant. This implies
that $M\in\mathcal{A}(G;C)$, contradicting the maximality of $N_{i}$. Thus
each $\mathcal{A}(G/N_{i},CN_{i}/N_{i})=\\{\\{1\\}\\}$. ∎

###  3.3. Transitive inverse-closed generating sets for a given group

Inverse-closed generating sets for a group $G$, that are transitive in the
sense of Definition 2.1, are often fairly natural subsets. For example we may
take a full conjugacy class of involutions in a nonabelian simple group $G$.
_Let $\mathcal{T}(G)$ denote the set of all transitive, inverse-closed
generating sets for $G$._ First we observe some simple properties of
$\mathcal{T}(G)$.

######  Lemma 3.3.

Let $G,H$ be nontrivial finite groups. Then

  1. (a)

$\mathcal{T}(G)$ is ${\rm Aut}(G)$-invariant; and

  2. (b)

if $C\in\mathcal{T}(G)$ and $D\in\mathcal{T}(H)$, and if either ${\rm
Aut}(G;C)$ is transitive on $C$ or ${\rm Aut}(H;D)$ is transitive on $D$, then
$C\times D\in\mathcal{T}(G\times H)$.

###### Proof.

(a) It is easy to check that, for $\sigma\in{\rm Aut}(G)$ and
$C\in\mathcal{T}(G)$, the image $C^{\sigma}$ is an inverse-closed generating
set for $G$. Further, $C^{\sigma}$ is ${\rm Aut}(G;C^{\sigma})$-invariant
(since $C$ is ${\rm Aut}(G;C)$-invariant), and the fact that $C$ is transitive
implies that $C^{\sigma}$ is transitive. Thus $C^{\sigma}\in\mathcal{T}(G)$.

(b) Suppose that $C\in\mathcal{T}(G)$ and $D\in\mathcal{T}(H)$. Then $C\times
D$ is inverse closed, and generates $G\times H$. Also ${\rm
Aut}(G;C)\times{\rm Aut}(H;D)\leq{\rm Aut}(G\times H;C\times D)$. If both
${\rm Aut}(G;C)$ is transitive on $C$ and ${\rm Aut}(H;D)$ is transitive on
$D$, then ${\rm Aut}(G;C)\times{\rm Aut}(H;D)$ is transitive on $C\times D$,
and hence $C\times D\in\mathcal{T}(G\times H)$. Suppose next that ${\rm
Aut}(G;C)$ is transitive on $C$ and ${\rm Aut}(H;D)$ has two orbits on $D$,
namely $D_{0}$ and $D_{0}^{-1}$. Then $C\times D_{0}$ and $C\times D_{0}^{-1}$
are the two orbits of ${\rm Aut}(G;C)\times{\rm Aut}(H;D)$ in $C\times D$, and
$(C\times D_{0})^{-1}=C\times D_{0}^{-1}$ since $C$ is inverse-closed. So
again $C\times D\in\mathcal{T}(G\times H)$, and the same argument works in the
case where ${\rm Aut}(H;D)$ is transitive on $D$ but ${\rm Aut}(G;C)$ is not
transitive on $C$. ∎

We note that the argument in the proof of part (b) does not extend to the case
where both ${\rm Aut}(G;C)$ is not transitive on $C$ and ${\rm Aut}(H;D)$ is
not transitive on $D$, since in this case ${\rm Aut}(G;C)\times{\rm Aut}(H;D)$
has four orbits in $C\times D$.

We now give a family of examples to illustrate that a group may have several
transitive inverse-closed generating sets, and in particular that some may be
properly contained in others.

######  Example 3.4.

Let $G=\langle a,b\mid a^{n}=b^{2}=1,bab=a^{-1}\rangle$, the dihedral group
$D_{2n}$ of order $2n\geq 6$, as in (4), and note that ${\rm Aut}(G)$ is given
in (6). Consider the inverse-closed generating set $C_{2}=\\{b,ba\\}$ as in
Example 2.3.

  1. (a)

As we saw in Example 2.3, ${\rm
Aut}(G;C_{2})=\langle\tau_{n-1}\varphi\rangle\cong Z_{2}$ (with
$\tau_{n-1},\varphi$ as in (5)), and $\tau_{n-1}\varphi$ interchanges the two
involutions in $C_{2}$. Hence $C_{2}$ is a transitive inverse-closed
generating set for $G$, that is, $C_{2}\in\mathcal{T}(G)$.

  2. (b)

By Lemma 3.3(a), for each $i=0,\dots,n-1$, the set
$D_{i}:=C_{2}^{\varphi^{i}}=\\{ba^{i},ba^{i+1}\\}\in\mathcal{T}(G)$. We note
that each of these $n$ subsets $D_{i}$ has size $2$, and each of the $n$ non-
central involutions $ba^{j}$ lies in exactly two of them.

  3. (c)

A larger natural subset lying in $\mathcal{T}(G)$ is $C^{\prime}=\\{ba^{i}\mid
0\leq i\leq n-1\\}$, the set of all non-central involutions in $G$: this set
$C^{\prime}$ forms a single orbit of ${\rm Aut}(G)$, and hence ${\rm
Aut}(G;C^{\prime})={\rm Aut}(G)$ and $C^{\prime}\in\mathcal{T}(G)$.

  4. (d)

The generating sets in (b) and (c) correspond to quite different normal edge-
transitive Cayley graphs: each ${\rm Cay}(G;D_{i})\cong C_{2n}$ (a cycle on
$2n$ vertices), while ${\rm Cay}(G;C^{\prime})\cong K_{n,n}$ (a complete
bipartite graph).

##  4\. Transitive inverse-closed generating sets for dihedral groups

It is instructive to take the analysis in Section 3 further and characterise
the set $\mathcal{T}(G)$ for groups $G$ in some specific infinite families. We
do this in Theorem 4.1 for the family of dihedral groups, which in particular
helps place the graphs in Example 3.4 into a broader context. We note that
Talebi [13, Theorem 3.3] showed that the only normal edge-transitive Cayley
graph ${\rm Cay}(D_{2n};C)$ of valency $n$ is the graph in Example 3.4(d):
this example arises in part (c) of Theorem 4.1.

######  Theorem 4.1.

Let $G=\langle a,b\mid a^{n}=b^{2}=1,bab=a^{-1}\rangle$, the dihedral group
$D_{2n}$ of order $2n\geq 6$, as in $\eqref{eqd}$, with ${\rm Aut}(G)$ as in
$\eqref{eqautd}$. Let $C\in\mathcal{T}(G)$, $A_{0}={\rm Aut}(G;C)$, and
$A_{0}\cap\langle\varphi\rangle=\langle\varphi^{r}\rangle$ where $r$ divides
$n$.

  1. (a)

Then there exists a non-empty subset $I\subseteq\\{0,1,\dots,r-1\\}$ such that
$C=\cup_{i\in I}ba^{i}\langle a^{r}\rangle$, and
$A_{0}/\langle\varphi^{r}\rangle$ acts transitively on the set
$\mathcal{S}=\\{ba^{i}\langle a^{r}\rangle|i\in I\\}$.

  2. (b)

Up to isomorphism (that is replacing $C$ by $C^{\sigma}$ for some
$\sigma\in{\rm Aut}(G)$), we may assume that $0\in I$.

  3. (c)

If $I=\\{0\\}$, then $r=1$, and $C$ is as in Example 3.4(c), with $A_{0}={\rm
Aut}(G)$.

  4. (d)

If $I=\\{0,i\\}$, for some $i\neq 0$, then $\gcd(i,r)=1$, there exists a
positive integer $k<n$ such that $\gcd(k,n)=1$ and $r\mid(k+1)$, and
$C=b\langle a^{r}\rangle\cup ba^{i}\langle a^{r}\rangle$ with
$\langle\varphi^{r},\tau_{k}\varphi^{i}\rangle$ a subgroup of $A_{0}$ acting
transitively on $C$. In particular if $r=n$, then for some $\sigma\in{\rm
Aut}(G)$, $C^{\sigma}=\\{b,ba\\}$ as in Example 3.4(a), with
$A_{0}^{\sigma}=\langle\tau_{n-1}\varphi\rangle\cong Z_{2}$.

###### Proof.

(a) Recall the explicit description of ${\rm Aut}(G)$ given in (5) and (6).
Let $C\in\mathcal{T}(G)$. Since $C$ generates $G$, it follows that $C$ must
contain an element of $G\setminus\langle a\rangle$, the set of $n$ non-central
involutions of $G$. Then since $C$ is a transitive inverse-closed generating
set for $G$ and $C$ contains an involution, it follows from Definition 2.1
that $A_{0}$ is transitive on $C$ so $C\subseteq G\setminus\langle
a\rangle=b\langle a\rangle$. Now $A_{0}$ contains $\langle\varphi^{r}\rangle$
and the $\langle\varphi^{r}\rangle$-orbits in $b\langle a\rangle$ are the
cosets $ba^{i}\langle a^{r}\rangle$ for $0\leq i\leq r-1$. Thus $C=\cup_{i\in
I}ba^{i}\langle a^{r}\rangle$ for some $I\subseteq\\{0,1,\dots,r-1\\}$. The
normal subgroup $\langle\varphi^{r}\rangle$ of $A_{0}$ fixes each of these
cosets setwise, and so, since $A_{0}$ is transitive on $C$, it follows that
$A_{0}/\langle\varphi^{r}\rangle$ acts transitively on the set $\mathcal{S}$,
proving part (a).

(b) By Lemma 3.3(a), the image of $C$ under any element of ${\rm Aut}(G)$ is
again an element of $\mathcal{T}(G)$. Let $i\in I$. Then, by (5),
$\varphi^{n-i}$ maps $ba^{i}$ to $b$ and hence maps $ba^{i}\langle
a^{r}\rangle$ to $ba^{0}\langle a^{r}\rangle$. Thus we may assume that $0\in
I$, proving (b).

(c) Suppose that $I=\\{0\\}$, that is, $C=b\langle a^{r}\rangle$. Since $C$ is
a generating set for $G$ it follows that $G=\langle b,a^{r}\rangle$ and hence
(since $r$ divides $n$) that $r=1$. Thus $C$ is the set of all non-central
involutions in $G$, as in Example 3.4(c), and $A_{0}={\rm Aut}(G)$, proving
(c).

(d) Suppose that $I=\\{0,i\\}$ for some $i\neq 0$, that is, $C=b\langle
a^{r}\rangle\cup ba^{i}\langle a^{r}\rangle$. Since $C$ is a generating set
for $G$ it follows that $G=\langle b,a^{r},a^{i}\rangle$ and hence
$a\in\langle a^{r},a^{i}\rangle$. This implies that $\gcd(i,r)=1$. Now $A_{0}$
is transitive on $C$, and since $\langle\varphi^{r}\rangle$ fixes each
$\langle a^{r}\rangle$-coset setwise, it follows that there exist $k,j$ with
$1\leq k\leq n-1$, $\gcd(k,n)=1$, and $0\leq j\leq r-1$, such that
$\tau_{k}\varphi^{j}\in A_{0}\setminus\langle\varphi^{r}\rangle$ and
$\tau_{k}\varphi^{j}$ interchanges $b\langle a^{r}\rangle$ and $ba^{i}\langle
a^{r}\rangle$. By (5), $\tau_{k}\varphi^{j}:b\to ba^{j}$ and hence $j=i$
(recall $0\leq j<r$). Also $\tau_{k}\varphi^{i}:ba^{i}\to ba^{i(k+1)}$ and
hence $ba^{i(k+1)}\in b\langle a^{r}\rangle$. This implies that $r$ divides
$i(k+1)$ and since $\gcd(i,r)=1$ this means that $r\mid(k+1)$. If these
conditions on $k$ are satisfied then
$A_{1}:=\langle\varphi^{r},\tau_{k}\varphi^{i}\rangle$ is a subgroup of
$A_{0}$ that acts transitively on $C$. Finally if $r=n$, then
$C=\\{b,ba^{i}\\}$ and $\gcd(i,n)=1$. Thus there exists $\ell$ such that
$1\leq\ell\leq n-1$ and $i\ell\equiv 1\pmod{n}$, and hence $\tau_{\ell}\in
T<{\rm Aut}(G)$ and $\tau_{\ell}:b\to b,ba^{i}\to ba$. Therefore
$C^{\tau_{\ell}}=\\{b,ba\\}$, as in Example 3.4(a). The subgroup of index 2 in
$A_{0}$ which fixes $C$ pointwise must fix each of $a,b$ and hence must be
trivial. It follows that $A_{0}\cong Z_{2}$, and in fact
$A_{0}^{\tau_{\ell}}={\rm
Aut}(G;C^{\tau_{\ell}})=\langle\tau_{n-1}\varphi\rangle$. ∎

###  4.1. Four-valent normal edge-transitive Cayley graphs of dihedral groups

For the special case where $n$ is an odd prime, Talebi [13, Theorem 3.5]
classified the $4$-valent normal edge-transitive Cayley graphs of $D_{2n}$, or
equivalently, the subsets of $\mathcal{T}(D_{2n})$ of cardinality $4$. We will
complete this classification for arbitrary $n$. Recall (4)-(6), and in
particular

$G=\langle a,b\mid a^{n}=b^{2}=1,bab=a^{-1}\rangle$

and ${\rm Aut}(G)=A\rtimes T$ with generators as in (6), so that, for $k$ with
$\gcd(k,n)=1$ and all $i,j$,

(7)
$(a^{i})^{\tau_{k}\varphi^{j}}=a^{ik},\quad(ba^{i})^{\tau_{k}\varphi^{j}}=ba^{ik+j}.$

Let $C\in\mathcal{T}(G)$ of cardinality $|C|=4$, so that $\Gamma:={\rm
Cay}(G,C)$ is a $4$-valent normal edge-transitive Cayley graph for $G$. All
such graphs are of this form. By Theorem 4.1(b), up to isomorphism we may (and
shall) assume that $b\in C$. In [13, Conjecture, p.451] Talebi conjectures
that each example must belong to one of two families which we describe in
Example 4.2. (Note that there are two misprints in line 3 of [13, Conjecture,
p.451], namely the symbol $p$ should be $n$, and the second family should be
the one given in [13, Theorem 3.4].)

######  Example 4.2.

Let $G=D_{2n}$ and ${\rm Aut}(G)$ be as above, with $n\geq 3$, and define $C$
as in (a) or (b).

  1. (a)

$C=\\{b,ba,ba^{i},ba^{1-i}\\}$, where $2\leq i\leq n-1$ such that
$\gcd(2i-1,n)=1$ and $2i(i-1)\equiv 0\pmod{n}$;

  2. (b)

$C=\\{b,ba,ba^{k+1},ba^{k^{2}+k+1}\\}$, where $1\leq k\leq n-2$,
$\gcd(k,n)=1$, and $1+k+k^{2}+k^{3}\equiv 0\pmod{n}$.

We establish some properties of these examples. In particular we decide when a
subset $C$ arises in more than one way in Example 4.2. The fact that
$C\in\mathcal{T}(G)$ for these subsets is proved in [13, Theorem 3.4] for $C$
in case (a), and in [13, Theorem 3.5] for $C$ in case (b) (but only if $n$ is
prime) by exhibiting certain elements of ${\rm Aut}(G;C)$. We determine the
subgroups ${\rm Aut}(G;C)$ completely, using the notation in (7).

######  Proposition 4.3.

Let $n,G,C$ be as in Example 4.2 (a) or (b), and let $A_{0}={\rm Aut}(G;C)$.
Then

  1. (a)

$|C|=4$ and $C\in\mathcal{T}(G)$. Moreover,

    1. (i)

if $C$ is as in Example 4.2 (a), then

$A_{0}=\begin{cases}\langle\tau_{n/2+1},\tau_{n-1}\varphi\rangle\cong
D_{8}&\text{if $i=n/2$ or $n/2+1$, and $n\equiv 0\pmod{4}$,}\\\
\langle\tau_{n-1}\varphi,\tau_{2i-1}\varphi^{1-i}\rangle\cong Z_{2}\times
Z_{2}&\text{otherwise};\end{cases}$

    2. (ii)

if $C$ is as in Example 4.2 (b), then

$A_{0}=\begin{cases}\langle\tau_{n/2+1},\tau_{n/2-1}\varphi\rangle\cong
D_{8}&\text{if $k=n/2-1$ and $n\equiv 0\pmod{4}$,}\\\
\langle\tau_{k}\varphi\rangle\cong Z_{4}&\text{otherwise}.\end{cases}$

  2. (b)

$C$ arises in both cases (a) and (b) of Example 4.2 if and only if $n\equiv
0\pmod{4}$ and $C=\\{b,ba,ba^{n/2},ba^{n/2+1}\\}$, which lies in Example 4.2
(a) with $i=n/2$ or $i=n/2+1$, and in Example 4.2 (b) with $k=n/2-1$.

  3. (c)

if $C$ is as in Example 4.2 (b) then the parameter $k$ is uniquely determined;
while if $C$ is as in Example 4.2 (a), then $C$ arises for exactly two
parameters $i,j$, namely
$C=\\{b,ba,ba^{i},ba^{1-i}\\}=\\{b,ba,ba^{j},ba^{1-j}\\}$ where $i+j=n+1$.

###### Proof.

(a) First we prove that $|C|=4$. The conditions on the parameters $i,k$ in
Example 4.2 imply that the first three elements of $C$ are pairwise distinct.
In case (a) if $ba^{1-i}$ is equal to one of the other elements of $C$ then
that element must be $ba^{i}$ and $i\equiv 1-i\pmod{n}$, so $i=(n+1)/2$.
However the conditions on $i$ then imply that $n$ divides $i-1$, which is a
contradiction. In case (b), if $ba^{k^{2}+k+1}$ is equal to one of the other
elements of $C$ then $n$ divides $k^{2}+k+1,k^{2}+k,k^{2}$ according as that
element is $b,ba,ba^{k+1}$, respectively, and then the fact that
$1+k+k^{2}+k^{3}\equiv 0\pmod{n}$ implies that $n$ divides $1,k+1,k+1$
respectively, contradicting the fact that $1\leq k\leq n-2$. Thus $|C|=4$.

Now $A_{0}$ contains the following subgroup $B$ acting regularly on $C$ (which
can be checked using (7)): for $C$ in case (a),
$B=\langle\tau_{n-1}\varphi,\tau_{2i-1}\varphi^{1-i}\rangle\cong Z_{2}\times
Z_{2}$ (noting that, under the conditions in case (a),
$(\tau_{n-1}\varphi)^{2}=(\tau_{2i-1}\varphi^{1-i})^{2}=1$ and the two
generators commute); and for $C$ in case (b),
$B=\langle\tau_{k}\varphi\rangle\cong Z_{4}$ (noting the conditions on $k$).
Thus $C\in\mathcal{T}(G)$. Also, since $B$ is transitive on $C$, we have a
factorisation $A_{0}=B(A_{0})_{b}$, and the stabiliser $(A_{0})_{b}$ is
contained in $({\rm Aut}(G))_{b}=T$, as defined in (6). The stabiliser of $ba$
in $(A_{0})_{b}$ fixes both $b$ and $a$, and hence is trivial, so
$|(A_{0})_{b}|\leq 3$. Suppose that $(A_{0})_{b}\neq 1$. As this subgroup is
contained in $T$, each nontrivial element is equal to $\tau_{\ell}$, for some
$\ell$ with $\gcd(\ell,n)=1$ and $1<\ell<n$, and we have
$(ba)^{\tau_{\ell}}=ba^{\ell}\in C\setminus\\{b,ba\\}$.

Suppose first that $C$ is in case (a), so $ba^{\ell}\in\\{ba^{i},ba^{1-i}\\}$.
Consider first the possibility $ba^{\ell}=ba^{i}$. Then $\ell=i$ (since
$1<i,\ell<n$) so $\gcd(i,n)=1$ and hence, by the condition on $i$ in Example
!4.2, $2(i-1)\equiv 0\pmod{n}$. However $0<2(i-1)<2n$ and it follows that
$2(i-1)=n$, so $n$ is even and $\ell=i=n/2+1$. Since $\gcd(\ell,n)=1$ and $n$
is even, this means in particular that $\ell$ is odd and hence $n\equiv
0\pmod{4}$. Thus $\tau_{\ell}^{2}=1$ and
$A_{0}=B\langle\tau_{\ell}\rangle=\langle\tau_{n-1}\varphi,\varphi^{n/2},\tau_{n/2+1}\rangle=\langle\tau_{n/2+1},\tau_{n-1}\varphi\rangle\cong
D_{8}$, as in (a)(i) (noting that
$\tau_{n/2+1}(\tau_{n-1}\varphi)=\tau_{n/2-1}\varphi$ and
$(\tau_{n/2-1}\varphi)^{2}=\varphi^{n/2}$). Similarly if $ba^{\ell}=ba^{1-i}$
then $\ell=n+1-i$ (since $1<i,\ell<n$), and this time $\gcd(i-1,n)=1$, so by
the condition on $i$ in Example !4.2, $2i\equiv 0\pmod{n}$, yielding $i=n/2$
and $\ell=n/2+1$. Again since $\gcd(\ell,n)=1$ and $n$ is even, we must have
$\ell$ odd and $n\equiv 0\pmod{4}$. The rest of the argument is the same, and
we find that $A_{0}$ is as in (a)(i). These arguments also show that, if $C$
is as in (a), and if in addition $n\equiv 2\pmod{4}$ whenever $i=n/2$ or
$n/2+1$, then $A_{0}=B$ as in (a)(i).

Suppose now that $C$ is in case (b), so
$ba^{\ell}\in\\{ba^{k+1},ba^{k^{2}+k+1}\\}$. We claim that $ba^{\ell}\neq
ba^{k+1}$. Suppose to the contrary that $ba^{\ell}=ba^{k+1}$, so $\ell=k+1$
and $\gcd(k+1,n)=1$. Since $n$ divides $k^{3}+k^{2}+k+1=(k^{2}+1)(k+1)$ it
follows that $k^{2}+1\equiv 0\pmod{n}$. Thus $ba^{k^{2}+k+1}=ba^{k}$, and is
mapped by $\tau_{\ell}$ to $ba^{k\ell}=ba^{k^{2}+k}=ba^{k-1}$. Hence
$ba^{k-1}=ba$ or $ba^{k+1}$. If $ba^{k-1}=ba$ then $k=2,\ell=3,n=k^{2}+1=5$,
but then $\tau_{\ell}:ba\to ba^{3}\to ba^{4}\to ba^{2}\to ba$ does not fix $C$
setwise. Thus $ba^{k-1}=ba^{k+1}$, but this implies that $a^{2}=1$ so $n=2$,
which is a contradiction, proving the claim. Therefore
$ba^{\ell}=ba^{k^{2}+k+1}$, and no element of $B$ maps $ba$ to $ba^{k+1}$.
This means that $\tau_{\ell}$ must interchange $ba$ and $ba^{k^{2}+k+1}$ and
fix $ba^{k+1}$. Thus $ba^{k+1}=(ba^{k+1})^{\tau_{\ell}}=ba^{(k+1)\ell}$ and
hence $k+1\equiv(k+1)(k^{2}+k+1)\equiv k^{2}+k\pmod{n}$ (using the condition
on $k$ in Example 4.2), so $k^{2}\equiv 1\pmod{n}$ and $\ell\equiv
k^{2}+k+1\equiv k+2\pmod{n}$. Now the condition in Example 4.2) becomes
$0\equiv k^{3}+k^{2}+k+1\equiv 2k+2\pmod{n}$, so $n=2(k+1)/r$ for some integer
$r$, and since $k+1<n$ this implies that $r=1$ so $n$ is even and $k=n/2-1$,
$\ell=n/2+1$. Further, since $n$ divides $k^{2}-1$ we must have $n\equiv
0\pmod{4}$, and so $A_{0}=\langle\tau_{n/2-1}\varphi,\tau_{n/2+1}\rangle\cong
D_{8}$ (note that $(\tau_{n/2-1}\varphi)^{2}=\varphi^{n/2}$ and the involution
$\tau_{n/2+1}$ inverts $\tau_{n/2-1}\varphi$). Thus (a)(ii) holds. In case
(b), for all other $k,n$ the group $A_{0}$ is equal to $B$ and again (a)(ii)
holds.

(b) Suppose next that $C$ arises in both cases (a) and (b) of Example 4.2 for
some $i,k$, respectively. Then $ba^{k+1}$ is equal to either $ba^{i}$ or
$ba^{1-i}$. In either case the condition $2i(i-1)\equiv 0\pmod{n}$ implies
that $n$ divides $2k(k+1)$. Since $(k+1)(k^{2}+1)=1+k+k^{2}+k^{3}\equiv
0\pmod{n}$, it follows that $n$ divides $(k+1)(2k^{2}-2(k^{2}+1))=-2(k+1)$.
Thus, since $1\leq k\leq n-2$, we must have $n=2(k+1)$, and so $n$ is even,
$k=n/2-1$, and $i=n/2$ or $i=n/2+1$ according as $ba^{k+1}=ba^{i}$ or
$ba^{1-i}$. The condition in Example 4.2 (b) on $k$ implies that
$\gcd(k,n)=1$, and since $n$ is even this means that $k$ is odd, and hence
$n/2$ is even, that is $n\equiv 0\pmod{4}$, and part (b) holds. The converse
is easily checked.

(c) Suppose that
$C=\\{b,ba,ba^{k+1},ba^{k^{2}+k+1}\\}=\\{b,ba,ba^{\ell+1},ba^{\ell^{2}+\ell+1}\\}$,
where $1\leq k,\ell\leq n-2$, $k\neq\ell$, and $1+k+k^{2}+k^{3}\equiv
1+\ell+\ell^{2}+\ell^{3}\equiv 0\pmod{n}$. Then $ba^{k+1}\neq ba^{\ell+1}$ and
so $ba^{k+1}=ba^{\ell^{2}+\ell+1}$, and hence
$k+1\equiv\ell^{2}+\ell+1\pmod{n}$. Similarly $k^{2}+k+1\equiv\ell+1\pmod{n}$.
Thus, using $1+k+k^{2}+k^{3}\equiv 0\pmod{n}$ repeatedly we have

$k\equiv\ell(\ell+1)\equiv(k^{2}+k)(k^{2}+k+1)\equiv
k^{3}+k^{2}\equiv-k-1\pmod{n}$

so $n$ divides $2k+1$. Since $1<2k+1<2n$ this implies that $n=2k+1$. A similar
computation yields $n=2\ell+1$, so $k=\ell$, which is a contradiction. This
proves the first assertion in part (c).

Finally suppose that
$C=\\{b,ba,ba^{i},ba^{1-i}\\}=\\{b,ba,ba^{j},ba^{1-j}\\}$, where $2\leq
i<j\leq n-1$ such that $\gcd(2i-1,n)=\gcd(2j-1,n)=1$ and $2i(i-1)\equiv
2j(j-1)\equiv 0\pmod{n}$. Then $ba^{i}\in\\{ba^{j},ba^{1-j}\\}$, and since
$ba^{i}\neq ba^{j}$ (as $1<i<j<n$), we must have $ba^{i}=ba^{1-j}$ which
implies that $i=n+1-j$. Conversely if $C=\\{b,ba,ba^{i},ba^{1-i}\\}$ is as in
Example 4.2(a) and we set $j=n+1-i$ then $2\leq j\leq n-1$, $\gcd(2j-1,n)=1$
and $2j(j-1)\equiv 0\pmod{n}$. Thus $C$ can be written with either parameter
$i$ or $j$. Note that $i,j$ are distinct since $i=j=n+1-i$ implies that
$2i-1=n$, which contradicts the condition $\gcd(2i-1,n)=1$. ∎

######  Remark 4.4.

(a) It follows from Proposition 4.3(c) that, if $C$ is as in Example 4.2 (a),
then we may assume that the parameter $i$ satisfies $1\leq i\leq n/2$.

(b) We note that there are infinitely many possibilities arising from Example
4.2 (a), for example, for each even $n\geq 4$ we may take $i=n/2$. On the
other hand $n$ cannot be an odd prime power, but some odd composite integers
$n$ are possible, for example $n=21,i=7$ gives an example. Similarly there are
infinitely many examples arising from Example 4.2 (b), namely, for each $k\geq
2$, we may take $n=k^{2}+1$, or indeed we may take $n=d(k^{2}+1)$ for any
divisor $d$ of $k+1$.

(c) We note that, by Proposition 4.3(a)-(b), taking $n=4$ and $k=1$ in Example
4.2 (b), or $n=4$ and $i=1$ or $2$ in Example 4.2 (a), we obtain the graph
${\rm Cay}(D_{8},C)\cong K_{4,4}$ with
$A_{0}=\langle\tau_{3},\varphi\rangle={\rm Aut}(D_{8})\cong D_{8}$.

(d) In his conjecture Talebi writes $p$ in place of $n$ for the subsets we
describe in Example 4.2(b), and we believe this is simply a misprint. These
examples for $n$ prime were identified in [13, Theorem 3.5], but they
definitely can arise for composite values of $n$. For example, as noted in
part (b).

In addition to the two infinite families of examples presented in Example 4.2,
we have identified a third family of examples and we describe these next.

######  Example 4.5.

Let $G=D_{2n}$ and ${\rm Aut}(G)$ be as above, with $n\geq 5$, and define
$C=\\{b,ba^{i},ba^{j},ba^{k}\\}$, where

  1. (i)

$1<i,j,k<n$ such that $i,j,k$ are pairwise coprime;

  2. (ii)

$\gcd(x,n)>1$ for each $x\in\\{i,j,k\\}$; and moreover

  3. (iii)

there exist $\ell,m$ such that $\ell^{2}\equiv m^{2}\equiv 1\pmod{n}$ and
$\ell,m,\ell m\not\equiv 1\pmod{n}$, and also $k\equiv j\ell+i\equiv
im+j\pmod{n}$ and $i(\ell+1)\equiv j(m+1)\equiv 0\pmod{n}$.

######  Remark 4.6.

We note that there are additional consequences of the congruence conditions
not written explicitly in Example 4.5. For example, since $\ell^{2}\equiv
1\pmod{n}$, we have $\gcd(\ell,n)=1$, and hence the congruence $k\equiv
j\ell+i\pmod{n}$ implies that $\gcd(k-i,n)=\gcd(j\ell,n)=\gcd(j,n)$; similarly
$\gcd(j-k,n)=\gcd(i,n)$. Also, using the congruences in part (iii), $j\equiv
j\ell^{2}\equiv(k-i)\ell\equiv k\ell+i\pmod{n}$, and so
$\gcd(i-j,n)=\gcd(-k\ell,n)=\gcd(k,n)$. We present a minimal set of conditions
in Example 4.5 to make checking as simple as possible.

######  Proposition 4.7.

Let $n,G,C,i,j,k,\ell,m$ be as in Example 4.5, and let $A_{0}={\rm Aut}(G;C)$.
Then

  1. (a)

$|C|=4$, $C\in\mathcal{T}(G)$, and if $n$ is even then
$n/2\not\in\\{i,j,k\\}$;

  2. (b)

$A_{0}=\langle\tau_{\ell}\varphi^{i},\tau_{m}\varphi^{j}\rangle\cong
Z_{2}\times Z_{2}$.

Moreover, $C^{\sigma}$ does not occur in Example 4.2, for any $\sigma\in{\rm
Aut}(G)$.

###### Proof.

By the conditions on $i,j,k$ it follows that $C$ consists of four pairwise
distinct involutions, and $C$ generates $G$. Next we show that, if $n$ is even
then $n/2\not\in\\{i,j,k\\}$. Suppose to the contrary that, say, $n=2i$. Then,
using the condition that $i,j$ are coprime, $\gcd(n,j)=\gcd(2i,j)=\gcd(2,j)$,
and hence since $\gcd(j,n)>1$ it follows that $j$ is even. A similar proof
shows that $k$ is even, and this is a contradiction since $j,k$ are coprime.

Now we check that both $\tau_{\ell}\varphi^{i}$ and $\tau_{m}\varphi^{j}$
leave $C$ invariant. Let $\sigma=\tau_{\ell}\varphi^{i}$. Then, using (7),
$b^{\sigma}=ba^{i}$, $(ba^{i})^{\sigma}=ba^{i\ell+i}=b$ (since
$i(\ell+1)\equiv 0\pmod{n}$), $(ba^{j})^{\sigma}=ba^{j\ell+i}=ba^{k}$ (since
$j\ell+i\equiv k\pmod{n}$), and $(ba^{k})^{\sigma}=ba^{k\ell+i}=ba^{j}$, since

$k\ell+i\equiv(j\ell+i)\ell+i=j\ell^{2}+i(\ell+1)\equiv j.1+0=j\pmod{n}.$

Hence $\sigma=\tau_{\ell}\varphi^{i}\in A_{0}$, and also $|\sigma|=2$ (since
$A_{0}$ is faithful on $C$). Now let $\sigma=\tau_{m}\varphi^{j}$. Then
$b^{\sigma}=ba^{j}$, $(ba^{j})^{\sigma}=ba^{jm+j}=b$ (since $j(m+1)\equiv
0\pmod{n}$), $(ba^{i})^{\sigma}=ba^{im+j}=ba^{k}$ (since $im+j\equiv
k\pmod{n}$), and $(ba^{k})^{\sigma}=ba^{km+j}=ba^{i}$, since

$km+j\equiv(im+j)m+j=im^{2}+j(m+1)\equiv i.1+0=i\pmod{n}.$

Hence $\sigma=\tau_{m}\varphi^{j}\in A_{0}$, and again, since $A_{0}$ is
faithful on $C$, we conclude that $|\tau_{m}\varphi^{j}|=2$ and $A_{0}$
contains $A:=\langle\tau_{\ell}\varphi^{i},\tau_{m}\varphi^{j}\rangle$. The
computations above show that the generators act on $C$ as double
transpositions and that, in this action, $A$ induces the Klein four group on
$C$. Since $A$ is faithful on $C$ it follows that $A\cong Z_{2}\times Z_{2}$,
and $A$ is transitive on $C$, so $C\in\mathcal{T}(G)$, proving part (a).

We claim that $A_{0}\cap\langle\varphi\rangle=1$. Suppose to the contrary that
$A_{0}$ contains $\varphi^{u}$ with $0<u<n$. By (5), for each $x$,
$(ba^{x})^{\varphi^{u}}=ba^{u+x}\neq ba^{x}$, and hence the permutation
induced by $\varphi^{u}$ on $C$ is either a product of two $2$-cycles, or a
$4$-cycle. In the former case, since $\varphi^{u}:b\to ba^{u}\to ba^{2u}$, we
have $b=ba^{2u}$ and hence $n$ divides $2u$. This implies that $n$ is even,
$u=n/2$, and $ba^{n/2}\in C$ so $n/2\in\\{i,j,k\\}$, which contradicts part
(a). Hence $\varphi^{u}$ induces a $4$-cycle on $C$, and since
$\varphi^{u}:b\to ba^{u}\to ba^{2u}\to ba^{3u}\to ba^{4u}$, it follows that
$n$ divides $4u$. Since the images $b,ba^{u},ba^{2u},ba^{3u}$ are pairwise
distinct, $n$ does not divide $2u$, so $n=4y$ where $y$ divides $u$. Without
loss of generality $i=u$ and $j\equiv 2u\pmod{n}$. Thus $y$ divides
$\gcd(i,j)$, and since $i,j$ are coprime this implies that $y=1$. Hence $n=4$,
which is a contradiction. Thus $A_{0}\cap\langle\varphi\rangle=1$. Therefore
$A_{0}\cong A_{0}\langle\varphi\rangle/\langle\varphi\rangle\leq{\rm
Aut}(G)/\langle\varphi\rangle\cong T$, as in (6). In particular $A_{0}$ is
abelian. Thus, since $A_{0}$ acts faithfully on $C$ and contains $A$, we
conclude that $A_{0}=A$, proving part (b).

Finally we prove the last assertion. Suppose to the contrary that, for some
$\sigma\in{\rm Aut}(G)$, the image $C^{\sigma}$ is as in Example 4.2. In
particular, $C^{\sigma}$ contains $b$ and $ba$. Since $A_{0}=Z_{2}\times
Z_{2}$, it follows from Proposition 4.3 that $C^{\sigma}$ is in Example
4.2(a). Suppose first that $\sigma=\varphi^{u}$ with $0\leq u<n$. Then
$C^{\sigma}$ consists of the four elements $(ba^{x})^{\sigma}=ba^{x+u}$ for
$x\in\\{0,i,j,k\\}$. If $u=0$ then $\sigma$ is the identity, and this is not
possible since $ba\not\in C$. Hence $u\neq 0$, so without loss of generality,
$b=ba^{i+u}$, that is $u\equiv-i\pmod{n}$. Then for some $x\in\\{0,j,k\\}$,
$ba=ba^{x+u}=ba^{x-i}$. However this implies that $x-i\equiv 1\pmod{n}$; and,
using Remark 4.6 and condition (ii) of Example 4.5, $\gcd(i,n)>1$,
$\gcd(j-i,n)=\gcd(k,n)>1$, and $\gcd(k-i.n)=\gcd(j,n)>1$, and we have a
contradiction. Hence $\sigma=\tau_{y}\varphi^{u}$ for some $y,u$ with
$\gcd(y,n)=1$ and $y\not\equiv 1\pmod{n}$. If $u=0$ then $b=b^{\sigma}$, and
without loss of generality $ba=(ba^{i})^{\sigma}=ba^{iy}$, implying that
$iy\equiv 1\pmod{n}$, which is not possible since $\gcd(i,n)>1$. Hence $u>0$
and without loss of generality we may assume that
$b=(ba^{i})^{\sigma}=ba^{iy+u}$, so $u\equiv-iy\pmod{n}$. Thus, for some
$x\in\\{0,j,k\\}$, $ba=(ba^{x})^{\sigma}=ba^{xy+u}=ba^{(x-i)y}$, which implies
that $\gcd(x-i,n)=1$, and the same argument which we just gave leads to a
contradiction. ∎

In Subsection 4.2 we exhibit an explicit infinite family of possibilities for
$C$ which satisfy all the conditions of Example 4.5. Thus this new
construction disproves Talebi’s conjecture. We now use the framework from
Theorem 4.1 to prove Theorem 1.4, which classifies all $4$-element subsets of
$\mathcal{T}(D_{2n})$, and hence all $4$-valent normal edge-transitive Cayley
graphs for dihedral groups.

###### Proof.

_of Theorem 1.4. _ Let $G=D_{2n}$ with $n\geq 3$, as in $\eqref{eqd}$, and
${\rm Aut}(G)$ as in $\eqref{eqautd}$. If $C$ is as in Example 4.2 or Example
4.5, then ${\rm Cay}(G;C)$ is a $4$-valent normal edge-transitive Cayley graph
by Proposition 4.3 or Proposition 4.7, respectively. The same is true for the
images of such subsets $C$ under elements of ${\rm Aut}(G)$, by Lemma 3.3(a).

Now we prove the converse. So suppose that $C$ is an inverse-closed generating
set for $G$ and ${\rm Cay}(G;C)$ is a $4$-valent normal edge-transitive Cayley
graph. Then $|C|=4$ and, by [11, Proposition 1(b)], $C\in\mathcal{T}(G)$. Let
$A_{0}={\rm Aut}(G;C)$, and
$A_{0}\cap\langle\varphi\rangle=\langle\varphi^{r}\rangle$ where $r$ divides
$n$. By Theorem 4.1, $C=\cup_{i\in I}ba^{i}\langle a^{r}\rangle$ for some
$I\subseteq\\{0,1,\dots,r-1\\}$ and we may assume that $0\in I$. Moreover,
$A_{0}/\langle\varphi^{r}\rangle$ acts transitively on the set
$\\{ba^{i}\langle a^{r}\rangle|i\in I\\}$. In particular
$4=|C|=|I|n/r\geq|I|$, so one of the following holds: (i) $I=\\{0\\}$ and
$r=n/4$, (ii) $|I|=2$ and $r=n/2$, or (iii) $|I|=4$ and $r=n$.

_Case (i)_ Here, by Theorem 4.1(c), $r=1$, so $n=4r=4$, $C=b\langle a\rangle$,
$A_{0}={\rm Aut}(G)$, and ${\rm Cay}(G;C)\cong K_{4,4}$, see Example 3.4(d).
By Remark 4.4, $C$ is as in Example 4.2.

_Case (ii)_ In this case $I=\\{0,i\\}$ for some $i$, and
$C=b\\{1,a^{i},a^{n/2},a^{n/2+i}\\}$. By Theorem 4.1(d),
$1=\gcd(i,r)=\gcd(i,n/2)$, and there exists a positive integer $k<n$ such that
$\gcd(k,n)=1$, and $r=n/2$ divides $k+1$. This implies that $k=n/2-1$ or
$k=n-1$. Moreover. by Theorem 4.1(d),
$B:=\langle\varphi^{n/2},\tau_{k}\varphi^{i}\rangle\leq A_{0}$ and $B$ acts
transitively on $C$.

Suppose first that $k=n/2-1$, so $n$ is even. Then, since $\gcd(k,n)=1$, it
follows that $k$ is odd, and hence $n\equiv 0\pmod{4}$ (since $k=n/2-1$). This
implies that $i$ is odd (since $\gcd(i,n/2)=1$), and hence $\gcd(i,n)=1$. Thus
there exists a positive integer $\ell<n$ such that $i\ell\equiv 1\pmod{n}$, so
$\gcd(\ell,n)=1$ and applying the map $\tau_{\ell}\in{\rm Aut}(G)$ defined in
(5) to $C$ we have $C^{\tau_{\ell}}=b\\{1,a,a^{n/2},a^{n/2+1}\\}$, as in
Example 4.2 (see Proposition 4.3(b)).

Suppose now that $k=n-1$. Again $n$ is even since $r=n/2$. Suppose first that
$\gcd(i,n)=1$. Then, as in the previous paragraph, there exists a positive
integer $\ell<n$ such that $i\ell\equiv 1\pmod{n}$ and $\gcd(\ell,n)=1$, and
hence $C^{\tau_{\ell}}=b\\{1,a,a^{n/2},a^{n/2+1}\\}$, as in Example 4.2.
Suppose on the other hand that $\gcd(i,n)>1$. Since $\gcd(i,n/2)=1$, this
implies that $i$ is even, $n/2$ is odd, and $\gcd(i,n)=2$. Thus there exists a
positive integer $\ell^{\prime}<n/2$ such that $i\ell^{\prime}\equiv
1\pmod{n/2}$, whence $\gcd(\ell^{\prime},n/2)=1$. If $\ell^{\prime}$ is odd
set $\ell=\ell^{\prime}$, and if $\ell^{\prime}$ is even set
$\ell=\ell^{\prime}+n/2$. Then in either case, $\ell$ is odd, $1\leq\ell<n$,
and $\gcd(\ell,n)=1$. Thus $\tau_{\ell}\in{\rm Aut}(G)$. Now we have
$i\ell\equiv 1\pmod{n/2}$ with $n/2,\ell$ odd and $n,i$ even; it follows that
$i\ell\equiv 1+n/2\pmod{n}$. Therefore
$(a^{i})^{\tau_{\ell}}=a^{i\ell}=a^{n/2+1},(a^{n/2})^{\tau_{\ell}}=a^{(n/2)\ell}=a^{n/2}$,
and $(a^{n/2+i})^{\tau_{\ell}}=a^{(n/2+i)\ell}=a^{n/2+n/2+1}=a$. Hence
$C^{\tau_{\ell}}=b\\{1,a,a^{n/2},a^{n/2+1}\\}$, as in Example 4.2.

_Case (iii)_ In this case $|I|=4$ and $r=n$, and we have
$C=b\\{1,a^{i_{1}},a^{i_{2}},a^{i_{3}}\\}$, for distinct $i_{1},i_{2},i_{3}$
between $1$ and $n-1$. Also $A_{0}\cap\langle\varphi\rangle=1$ so $A_{0}\cong
A_{0}\langle\varphi\rangle/\langle\varphi\rangle\leq{\rm
Aut}(G)/\langle\varphi\rangle\cong T$. In particular $A_{0}$ is abelian and
each nontrivial element of $A_{0}$ is of the form $\tau_{k}\varphi^{i}$ for
some $k,i$ with $\gcd(k,n)=1$ and $0\leq i<n$. Since $C$ generates $G$ it
follows that $A_{0}$ acts faithfully on $C$, so $A_{0}$ is a transitive
abelian permutation group on $C$. This implies that $|A_{0}|=4$ and either
$A_{0}$ is cyclic or a Klein four group.

Suppose first that $A_{0}$ is cyclic, say
$A_{0}=\langle\tau_{k}\varphi^{i}\rangle\cong Z_{4}$. Without loss of
generality we may assume that $\tau_{k}\varphi^{i}:b\to ba^{i_{1}}\to
ba^{i_{2}}\to ba^{i_{3}}\to b$. By (7), $i_{1}=i$, $i_{2}\equiv
i(k+1)\pmod{n}$, $i_{3}\equiv i(k^{2}+k+1)\pmod{n}$, and
$i(k^{3}+k^{2}+k+1)\equiv 0\pmod{n}$. This implies in particular that
$G=\langle C\rangle\leq\langle b,a^{i}\rangle$, and we conclude that
$\gcd(i,n)=1$. Thus there exists $\ell$ such that $\gcd(\ell,n)=1$ and
$i\ell\equiv 1\pmod{n}$, and replacing $C$ by $C^{\tau_{\ell}}$ we may assume
in addition that $i=1$. Hence $C$ is as in Example 4.2(b).

Suppose now that $A_{0}\cong Z_{2}\times Z_{2}$. Then $A_{0}$ has generators
$\tau_{\ell}\varphi^{i}$ and $\tau_{m}\varphi^{j}$ such that
$\tau_{\ell}\varphi^{i}:b\leftrightarrow ba^{i_{1}},ba^{i_{2}}\leftrightarrow
ba^{i_{3}}$ and $\tau_{m}\varphi^{j}:b\leftrightarrow
ba^{i_{2}},ba^{i_{1}}\leftrightarrow ba^{i_{3}}$. This implies that
$i_{1}=i,i_{2}=j$, $i_{3}\equiv j\ell+i\equiv im+j\pmod{n}$, and
$i(\ell+1)\equiv j(m+1)\equiv 0\pmod{n}$. Thus
$a^{i_{3}}=a^{j\ell+i}\in\langle a^{i},a^{j}\rangle$, and since $C$ generates
$G$ it follows that $G=\langle b,a^{i},a^{j}\rangle$, and hence $\gcd(i,j)=1$.
A similar argument shows that $\gcd(i,i_{3})=\gcd(j,i_{3})=1$. We will write
$k=i_{3}$, and we note that the third involution in $A_{0}$ is
$(\tau_{\ell}\varphi^{i})(\tau_{m}\varphi^{j})=\tau_{\ell
m}\varphi^{im+j}=\tau_{\ell m}\varphi^{k}$. Now
$(\tau_{\ell}\varphi^{i})^{2}=1$, and (5) implies that $\ell^{2}\equiv
1\pmod{n}$. Similarly $m^{2}\equiv(\ell m)^{2}\equiv 1\pmod{n}$. Also since
$A_{0}\cap\langle\varphi\rangle=1$ (as we are in case (iii)) we have
$\ell,m,\ell m\not\equiv 1\pmod{n}$. This means that all the conditions of
Example 4.5 parts (i) and (iii) hold. Using the congruences we have just
derived, we have, modulo $n$,

$k(\ell m+1)\equiv(im+j)(\ell m+1)=i\ell m^{2}+im+j\ell m+j\equiv-
im^{2}+im-j\ell+j\equiv-im^{2}+i=-i(m^{2}-1)\equiv 0.$

Thus the conditions on the pairs $(i,k),(j,\ell),(k,\ell m)$ are
‘symmetrical’.

We claim that, _if any one of $\gcd(i,n)=1$, $\gcd(j,n)=1$, or $\gcd(k,n)=1$,
then $C^{\sigma}$ is as in Example 4.2(a), for some $\sigma\in{\rm Aut}(G)$._
If $\gcd(i,n)=1$, then there exists $u$ such that $iu\equiv 1\pmod{n}$, and
the image of $C$ under $\tau_{u}$ is $\\{b,ba,ba^{ju},ba^{i_{3}u}\\}$. Similar
arguments show that, if $\gcd(j,n)=1$, or $\gcd(k,n)=1$, then the image of $C$
under some $\sigma\in{\rm Aut}(G)$ contains both $b$ and $ba$. Thus (because
of the symmetry of the conditions on $i,j,k$) in order to prove the claim we
may assume that $i=1$ and hence $2\leq j,k\leq n-1$. Then, since
$\ell+1=i(\ell+1)\equiv 0\pmod{n}$, we have $\ell=n-1$, and hence $k\equiv
j\ell+i\equiv-j+1\pmod{n}$. Since also $k\equiv im+j=m+j\pmod{n}$, we have
$m\equiv k-j\equiv 1-2j\pmod{n}$, so $\gcd(2j-1,n)=1$ and $0\equiv
j(m+1)\equiv 2j(1-j)\pmod{n}$. Thus $C=\\{b,ba,ba^{j},ba^{1-j}\\}$ is as in
Example 4.2(a), proving the claim.

To complete the proof of Theorem 1.4, we may therefore assume also that all
the conditions of Example 4.5 part (ii) hold, so $C$ is as in Example 4.5,
completing the proof of Theorem 1.4. ∎

###  4.2. Infinite family of Examples

By Remark 4.4(b), there are infinitely many $4$-valent normal edge-transitive
Cayley graphs of dihedral groups arising in each part of Example 4.2. Here we
present an explicit infinite family of examples for our new construction in
Example 4.5. Proof that we obtain infinitely many examples simply depends on
the fact that there are infinitely many odd primes $p$ not of the form
$p=2^{r}-1$, that is, primes which are not _Mersenne primes_.

######  Lemma 4.8.

There are infinitely many odd primes which are not Mersenne primes.

###### Proof.

This follows easily from the number theoretic result known as Bertrand’s
Postulate (see for example [9, Theorem 8.7]) that, for all integers $m\geq 3$
there exists a prime $p$ such that $m<p<2m$. Taking $m=2^{r}-1\geq 3$, we
obtain a prime satisfying $2^{r}-1<p<2^{r+1}-2$. Such a prime $p$ is odd and
is not a Mersenne prime, and the primes obtained for distinct integers $r\geq
2$ are pairwise distinct. ∎

######  Proposition 4.9.

Let $p$ be an odd prime that is not a Mersenne prime, and let $q$ be any odd
prime divisor of $p+1$. Define $n,i,j,k,\ell,m$ as follows:

$n=2pq,\ i=p,\ j=q,\ k=p+q,\ \ell=2p+1,\ m=n-\ell=2pq-2p-1.$

Then all the conditions of Example 4.5 hold for $i,j,k,\ell,m$, and in
particular $C=\\{b,ba^{i},ba^{j},ba^{k}\\}$ arises in Example 4.5 for the
group $G=D_{2n}$.

###### Proof.

Since $p,q$ are distinct odd primes it follows that $i,j,k$ are pairwise
coprime, so condition (i) of Example 4.5 holds. Next

$\gcd(i,n)=p,\quad\gcd(j,n)=q,\quad\gcd(k,n)=2,$

and hence condition (ii) of Example 4.5 holds. Now we check condition (iii) of
Example 4.5. Note that $p$ divides $\ell-1$ and $q$ divides $2(p+1)=\ell+1$,
and hence, since $\ell$ is odd, $n=2pq$ divides $\ell^{2}-1$, that is,
$\ell^{2}\equiv 1\pmod{n}$. Also $m^{2}\equiv 1\pmod{n}$ since
$m\equiv-\ell\pmod{n}$. By definition, $\ell,m\not\equiv 1\pmod{n}$, and we
have $\ell m\equiv-\ell^{2}\equiv-1\not\equiv 1\pmod{n}$. Next
$i(\ell+1)=p(2p+2)=2p(p+1)\equiv 0\pmod{n}$ since $q$ divides $p+1$, and
$j(m+1)=q(n-2p)\equiv-2pq\equiv 0\pmod{n}$. Also $j\ell+i=q(2p+1)+p\equiv
q+p=k\pmod{n}$. Finally $im+j=p(n-2p-1)+q\equiv-2p(p+1)+p+q\equiv
p+q=k\pmod{n}$, since $n$ divides $2p(p+1)$. Thus all the conditions of
Example 4.5 hold, so $C=\\{b,ba^{i},ba^{j},ba^{k}\\}$ arises in Example 4.5
for the group $G=D_{2n}$. ∎

##  5\. Graphs which are not normal edge-transitive

For an arbitrary inverse-closed generating set $C$ of a group $G$, it is of
course possible to define normal quotients of the Cayley graph ${\rm
Cay}(G;C)$ relative to ${\rm Aut}(G;C)$-invariant normal subgroups of $G$. One
may wonder to what extent Theorem 1.2 might extend to this general situation,
that is to say, whether or not the assumption that ${\rm Cay}(G;C)$ is normal
edge-transitive is needed. Here we consider a small example which pin-points
one of the problems which may cause the graph isomorphism in Theorem 1.2(ii)
to fail if ${\rm Cay}(G;C)$ is not normal edge-transitive. Recall that ${\sf
NormCay{CS}}$ is the class of connected normal edge-transitive Cayley graphs
for finite characteristically simple groups.

######  Example 5.1.

Let
$G=\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}$
so that ${\rm Aut}(G)={\rm GL}(4,2)$, and define
$C=\\{a_{1},a_{2},b_{1},b_{2},b_{3}\\}$, where

$a_{1}=(1,0,1,1),\ a_{2}=(0,1,1,1),\ b_{1}=(1,0,1,0),\ b_{2}=(0,1,0,1),\
b_{3}=(1,1,1,1),$

and set $A=\\{a_{1},a_{2}\\}$ and $B=\\{b_{1},b_{2},b_{3}\\}$, so $C=A\cup B$.
Define

$\displaystyle\tau_{1}$ $\displaystyle:(x,y,z,w)\to(y+z+w,x+z+w,z,w),$
$\displaystyle\tau_{2}$ $\displaystyle:(x,y,z,w)\to(x+z+w,x+w,w,x+y),\
\text{and}$ $\displaystyle\tau_{3}$ $\displaystyle:(x,y,z,w)\to(y,x,w,z).$

######  Proposition 5.2.

Let $G,C$ be as in Example 5.1, and let $A_{0}={\rm Aut}(G;C)$. Then

  1. (a)

$C$ is an inverse-closed generating set for $G$, and
$A_{0}=\langle\tau_{1}\rangle\times\langle\tau_{2},\tau_{1}\tau_{3}\rangle\cong{\rm
Sym}(A)\times{\rm Sym}(B)=S_{2}\times S_{3}$. In particular $A_{0}$ fixes each
of $A$ and $B$ setwise, and $C\not\in\mathcal{T}(G)$, that is, $C$ is not
transitive.

  2. (b)

$\mathcal{A}_{\max}(G;C)$ contains $M:=\langle
A\rangle\cong\mathbb{Z}_{2}^{2}$ and $N:=\langle
b_{1},b_{2},a_{1}+a_{2}\rangle\cong\mathbb{Z}_{2}^{3}$, and $\Phi(G;C)=M\cap
N=\langle a_{1}+a_{2}\rangle\cong\mathbb{Z}_{2}$.

  3. (c)

The graph $\Gamma:={\rm Cay}(G;C)$ is not normal edge-transitive; its normal
quotient graphs

$\Gamma_{M}:={\rm Cay}(G/M,(C+M)/M),\ \Gamma_{N}:={\rm
Cay}(G/N,(C+N)/N)\in{\sf NormCay{CS}},$

and moreover $\Gamma_{M}\cong K_{4}$, $\Gamma_{N}\cong K_{2}$, while for
$\Phi:=\Phi(G;C)$, $\Gamma_{\Phi}:={\rm Cay}(G/\Phi,(C+\Phi)/\Phi)$ is the
$4$-valent complement of the cube $Q_{3}$.

  4. (d)

The map $g\to(gM,gN)$ induces a group isomorphism $G/\Phi(G;C)\to G/M\times
G/N$, but does not induce a graph isomorphism from $\Gamma_{\Phi}$ to a
subgraph of the direct product $\Gamma_{M}\times\Gamma_{N}$. For example, a
‘$b_{3}$-type’ edge such as $\\{0+\Phi,b_{3}+\Phi\\}$ of $\Gamma_{\Phi}$ does
not map to an edge of $\Gamma_{M}\times\Gamma_{N}$ as it projects to a loop of
$\Gamma_{N}$.

###### Proof.

(a) The first assertion follows since each element of $G$ is equal to its
inverse, and since $C$ spans $G$ as a vector space. Next, to simplify our
later arguments, we check directly from their definitions that

$\displaystyle\tau_{1}$ $\displaystyle:a_{1}\leftrightarrow a_{2},\ b_{1}\to
b_{1},\ b_{2}\to b_{2},\ b_{3}\to b_{3}$ $\displaystyle\tau_{2}$
$\displaystyle:a_{1}\to a_{1},\ a_{2}\to a_{2},\ b_{1}\to b_{2}\to b_{3}\to
b_{1}$ $\displaystyle\tau_{3}$ $\displaystyle:a_{1}\leftrightarrow a_{2},\
b_{1}\leftrightarrow b_{2},\ b_{3}\to b_{3}.$

In particular each $\tau_{i}$ maps the spanning set $C$ bijectively to itself
and hence each $\tau_{i}\in{\rm GL}(4,2)$. Again, since each $\tau_{i}$ fixes
$C$ setwise (and moreover each $\tau_{i}$ fixes each of $A$ and $B$ setwise),
it follows that each $\tau_{i}\in A_{0}$. Now $A_{0}$ acts faithfully as a
permutation group on $C$, and hence it follows easily from the displayed
actions of the $\tau_{i}$ on $C$ that the subgroup they generate is
$H=\langle\tau_{1}\rangle\times\langle\tau_{2},\tau_{1}\tau_{3}\rangle\cong{\rm
Sym}(A)\times{\rm Sym}(B)=S_{2}\times S_{3}$. Moreover, this subgroup $H$ is a
maximal subgroup of ${\rm Sym}(C)=S_{5}$. If $A_{0}$ is strictly larger than
$H$, then we would have $A_{0}\cong{\rm Sym}(C)$, and hence $A_{0}$ would
contain an element $\varphi:b_{1}\to b_{1},\ b_{2}\to b_{2},\ b_{3}\to
a_{1}\to a_{2}\to b_{3}$. However such an element $\varphi$ must in particular
lie in ${\rm GL}(4,2)$ and hence

$\varphi(b_{3})=\varphi(b_{1}+b_{2})=\varphi(b_{1})+\varphi(b_{2})=b_{1}+b_{2}=b_{3},$

which is a contradiction. Hence $H=A_{0}$. Thus $A_{0}$ has orbits in $C$ of
lengths $2$ and $3$, and hence $C\not\in\mathcal{T}(G)$, that is, $C$ is not
transitive. This proves part (a).

(b) Let $M_{B}=\langle B\rangle=\\{0,b_{1},b_{2},b_{3}\\}$. Then $G=M+M_{B}$
and $M\cap M_{B}=0$. In particular each nontrivial coset of $M$ in $G$ is of
the form $b_{i}+M$ for some $i\leq 3$. Thus if $K$ is an $A_{0}$-invariant
normal subgroup of $G$ properly containing $M$ then $K=G$ since $A_{0}$ is
transitive on $B$ by part (a). It follows that $M\in\mathcal{A}_{\max}(G;C)$.
Next we deal with $N$. We see by its definition that $N=\\{(x+z,y+z,x,y)\mid
x,y,z\in\mathbf{F}_{2}\\}$. It follows from the actions of the $\tau_{i}$
displayed above that $\tau_{1}$ fixes $N$ pointwise, and that both $\tau_{2}$
and $\tau_{3}$ leave $N$ invariant. Hence $N$ is an $A_{0}$-invariant normal
subgroup of $G$, and as $N$ is maximal in $G$ we conclude that
$N\in\mathcal{A}_{\max}(G;C)$. We note that $M\cap N=\langle
a_{1}+a_{2}\rangle=\\{0,(1,1,0,0)\\}$ since $M\cap M_{B}=0$. Hence,
$\Phi(G;C)\leq M\cap N$, by (3), so to complete the proof of part (b) it
remains for us to show that $a:=a_{1}+a_{2}=(1,1,0,0)\in\Phi(G;C)$.

To do this, we need to check that the criterion of Theorem 1.1(b) holds for
$a$. So suppose that $X\subseteq G$ and that the normal $C$-closure of
$X\cup\\{a\\}$ generates $G$, that is, $G$ is generated by
$\widehat{X}:=\\{(x^{g})^{\sigma}|x\in X\cup\\{a\\},g\in G,\sigma\in
A_{0}\\}$. Since $G$ is abelian, and since $a=a_{1}+a_{2}$ is fixed by each
element of $A_{0}$ (by part (a)), $\widehat{X}=\\{a\\}\cup Y$, where
$Y=\\{(x^{g})^{\sigma}|x\in X,g\in G,\sigma\in A_{0}\\}$, that is, $Y$ is the
normal $C$-closure of $X$. We therefore need to prove that $Y$ generates $G$.
Suppose to the contrary that $W:=\langle Y\rangle$ is a proper subgroup of
$G$. Since $Y\cup\\{a\\}$ generates $G$ it follows that $G=W+\langle a\rangle$
and $W\cap\langle a\rangle=0$. In particular there exists $w\in W$ such that
$w+a=a_{1}$. This means that $W$ contains $w=a+a_{1}=a_{2}$, and since $Y$ is
$C$-closed and generates $W$, also $a_{1}=a_{2}^{\tau_{1}}$ lies in $W$, and
therefore $a=a_{1}+a_{2}\in W$, which is a contradiction. Thus we have proved
that $Y$ generates $G$, and hence that the criterion of Theorem 1.1(b) holds
for $a$. Therefore $a:=(1,1,0,0)\in\Phi(G;C)$. and part (b) is proved.

(c) By [11, Proposition 1(c)], the graph $\Gamma:={\rm Cay}(G;C)$ is not
normal edge-transitive since the set $C$ is not transitive (by part (a)).
Since $(C+M)/M=(B+M)/M$ (as $A\subset M$), and since $A_{0}$ is transitive on
$B$ by part (a), it follows that $\Gamma_{M}$ is normal edge-transitive (by
[11, Proposition 1(c)]), and hence $\Gamma_{M}\in{\sf NormCay{CS}}$. Similarly
$\Gamma_{N}\in{\sf NormCay{CS}}$ since $(C+N)/N=(A+N)/N$. Now $\Gamma_{M}\cong
K_{4}$ and $\Gamma_{N}\cong K_{2}$, since $(C+M)/M$ and $(C+N)/N$ consist of
all the nontrivial cosets of $G/M$ and $G/N$, respectively. On the other hand,
$(C+\Phi)/\Phi$ has size 4, since $a_{1}+\Phi=a_{2}+\Phi$ and this element is
distinct from each of the $b_{i}+\Phi$, which themselves are pairwise
distinct. Thus $\Gamma_{\Phi}$ has valency $4$, and it is not difficult to
check that $\Gamma_{\Phi}$ is the complement of the $3$-dimensional cube graph
$Q_{3}$.

(d) The map $\phi:g\to(gM,gN)$ is a group homomorphism $\phi:G\to G/M\times
G/N$ with kernel $M\cap N=\Phi(G;C)$ (by part (b)). Thus the image of $\phi$
is isomorphic to $G/\Phi(G;C)=G/(M\cap N)\cong\mathbb{Z}_{2}^{3}$. Since
$G/M\cong\mathbb{Z}_{2}^{2}$ and $G/N\cong\mathbb{Z}_{2}$, it follows that
$\phi$ is onto and $\phi$ induces a group isomorphism $G/\Phi(G;C)\cong
G/M\times G/N$. This bijection on vertices does not map all edges of
$\Gamma_{\Phi}$ to edges of the direct product $\Gamma_{M}\times\Gamma_{N}$,
as a ‘$b_{3}$-type’ edge $\\{x+\Phi,x+b_{3}+\Phi\\}$ is mapped to the vertex-
pair $\\{(x+M,x+N),(x+b_{3}+M,x+N)\\}$ (since $b_{3}\in N$), and this is not
an edge of the direct product $\Gamma_{M}\times\Gamma_{N}$. Put more simply,
$\Gamma_{\Phi}$ has valency $4$ and so is not isomorphic to a subgraph of the
valency $3$ direct product graph $\Gamma_{M}\times\Gamma_{N}$. ∎

## References

  * [1] C. Adiga, A. A. Talebi, and H. Ariamanesh, Some normal edge-transitive Cayley graphs on Frobenius groups $F_{p,3}$. Adv. Stud. Contemp. Math. (Kyungshang) 22 (2012), 439–443.
  * [2] X. Caicedo, Subdirect Decomposition of $n$-Chromatic Graphs, J. Alg. Comb. 8 (1998), 157–168.
  * [3] B. P. Corr, C. E. Praeger, Normal edge-transitive Cayley graphs of Frobenius groups, J. Alg. Comb.  42(3) (2015), 803–827.
  * [4] M. R. Darafsheh, A. Assari, Normal edge-transitive Cayley graphs on non-abelian groups of order $4p$, where $p$ is a prime number, Sci. China Math. 56 (2013), 213–219.
  * [5] M. R. Darafsheh, M. Yaghoobian, Tetravalent normal edge-transitive Cayley graphs on a certain group of order $6n$. Turkish J. Math. 41 (2017), 1354–1359.
  * [6] C. Godsil, On the full automorphism group of a graph, Combinatorica 1(3) (1981), 243–256.
  * [7] B. Huppert, Endliche Gruppen. I, Springer-Verlag, Berlin–New York, 1967.
  * [8] Behnam Khosravi, Behrooz Khosravi, and Bahman Khosravi, On reconstruction of normal edge-transitive Cayley graphs. Ann. Comb. 24 (2020), 791–807.
  * [9] I. Niven, H. S. Zuckerman, and H. L. Montgomery. _An Introduction to the Theory of Numbers_ , fifth edition, Wiley, New York, 1991.
  * [10] Y. Pakravesh, and A. Iranmanesh, Normal edge-transitive Cayley graphs on the non-abelian groups of order $4p^{2}$, where $p$ is a prime number. Bull. Iranian Math. Soc. 43 (2017), 951–974.
  * [11] C. E. Praeger, Finite Normal Edge-transitive Cayley graphs, Bull. Austral. Math. Soc. 60 (1999), 207–220.
  * [12] Hyo-Seob Sim and Young-Won Kim, Normal edge-transitive circulant graphs. Bull. Korean Math. Soc. 38 (2001), 317–324.
  * [13] A. A. Talebi, Some normal edge-transitive Cayley graphs on dihedral groups, The Journal of Mathematics and Computer Science 2 (2011), 448–452.