###### Abstract

Let $G$ be a (finite or infinite) group, and let
$K_{G}=\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ be
the complete graph with vertex set $G$, considered as a Cayley graph of $G$.
Being a Cayley graph, it has a natural edge-colouring by sets of the form
$\\{s,s^{-1}\\}$ for $s\in G$. We prove that every colour-permuting
automorphism of $K_{G}$ is an affine map, unless $G\cong Q_{8}\times B$, where
$Q_{8}$ is the quaternion group of order $8$, and $B$ is an abelian group,
such that $b^{2}$ is trivial for all $b\in B$.

We also prove (without any restriction on $G$) that every colour-permuting
automorphism of $K_{G}$ is the composition of a group automorphism and a
colour-preserving graph automorphism. This was conjectured by D. P. Byrne, M.
J. Donner, and T. Q. Sibley in 2013.

###### keywords:

Cayley graph, automorphism, colour-permuting, complete graph

Colour-permuting automorphisms of complete Cayley graphs

_To Dragan Marušič on his 70th birthday_

Shirin<EMAIL_ADDRESS>Dave Witte
<EMAIL_ADDRESS>https://deductivepress.ca/dmorris/ Department
of Mathematics and Computer Science, University of Lethbridge,
4401 University Drive, Lethbridge, Alberta, T1K 3M4, Canada

05C25, 05C15

##  0 Preliminaries

The statements of our main results use the following standard notation and
terminology.

######  Definition 1 ([8, pp. 189–191]).

Let $S$ be an inverse-closed subset of a group $G$. (This means that $s\in
S\Rightarrow s^{-1}\in S$.)

  1. 1.

The _Cayley graph_ of $G$, with respect to $S$, is the graph
$\operatorname{Cay}(G;S)$ whose vertices are the elements of $G$, and with an
edge from $g$ to $gs$, for each $g\in G$ and $s\in S$.

  2. 2.

$\operatorname{Cay}(G;S)$ has a natural edge-colouring. Namely, each edge of
the form $g\mathbin{\hbox{\vrule height=3.0pt,depth=-2.25pt,width=10.0pt}}gs$
is coloured with the set $\\{s,s^{-1}\\}$. (In order to make the colouring
well-defined, it is necessary to include $s^{-1}$, because
$g\mathbin{\hbox{\vrule height=3.0pt,depth=-2.25pt,width=10.0pt}}gs$ is the
same as the edge $gs\mathbin{\hbox{\vrule
height=3.0pt,depth=-2.25pt,width=10.0pt}}g$, which is of the form
$h\mathbin{\hbox{\vrule height=3.0pt,depth=-2.25pt,width=10.0pt}}hs^{-1}$,
with $h=gs$.)

  3. 3.

A function $\varphi\colon G\to G$ is said to be _affine_ if it is the
composition of an automorphism of $G$ with left translation by an element of
$G$. This means $\varphi(x)=\alpha(gx)$, for some
$\alpha\in\operatorname{Aut}G$ and $g\in G$.

  4. 4.

A Cayley graph $\operatorname{Cay}(G;S)$ is _CCA_ if all of its colour-
preserving automorphisms are affine functions on $G$. (CCA is an abbreviation
for the _Cayley Colour Automorphism_ property.)

  5. 5.

We say that $G$ is _CCA_ if every connected Cayley graph of $G$ is CCA.

  6. 6.

An automorphism $\varphi$ of a Cayley graph $\operatorname{Cay}(G;S)$ is
_colour-permuting_ if it respects the colour classes; this means that if two
edges have the same colour, then their images under $\varphi$ must also have
the same colour. Hence, there is a permutation $\pi$ of $S$, such that
$\varphi(gs)\in\\{\varphi(g)\,\pi(s)^{\pm 1}\\}$ for all $g\in G$ and $s\in S$
(and $\pi(s^{-1})=\pi(s)^{-1}$).

  7. 7.

$\operatorname{Cay}(G;S)$ is _strongly CCA_ if all of its colour-permuting
automorphisms are affine functions.

  8. 8.

We say that $G$ is _strongly CCA_ if every connected Cayley graph of $G$ is
strongly CCA.

  9. 9.

$\operatorname{Cay}(G;S)$ is _normal_ if every automorphism of
$\operatorname{Cay}(G;S)$ is an affine function (cf. [10, Definition 1] and
[7, Lemma 2.1]). ( _Warning:_ This terminology is not completely standard,
because some graph theorists use “normal” to mean that the connection set $S$
is a union of conjugacy classes [1, p. 2].)

##  1 Introduction

Many groups are CCA, but not strongly CCA. (The smallest example is the
dihedral group of order 12 [8, Prop. 7.3].) This means there are groups $G$,
such that every connected Cayley graph of $G$ is CCA, but not every connected
Cayley graph of $G$ is strongly CCA. The following result shows that this is
not true if we replace the universal quantifier with the existential
quantifier; that is, it shows that if there exists a Cayley graph of $G$ that
is CCA, then there exists a Cayley graph of $G$ that is strongly CCA.
(Specifically, the complete graph on $G$ is strongly CCA.)

######  Theorem 2.

If $G$ is a (finite or infinite) group, then the following are equivalent:

  1. 1.

$G$ has a Cayley graph that is strongly CCA.

  2. 2.

The complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is
strongly CCA.

  3. 3.

$G$ has a Cayley graph that is CCA.

  4. 4.

The complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is CCA.

  5. 5.

$G$ is not of the form $Q_{8}\times B$, where $Q_{8}$ is the quaternion group
of order $8$, and $B$ is an abelian group, such that $b^{2}$ is trivial for
all $b\in B$.

Furthermore, if $G$ is finite, then these are also equivalent to:

  1. 6.

Either $G$ has a Cayley graph that is normal, or
$G\cong\mathbb{Z}_{4}\times\mathbb{Z}_{2}$.

######  Note 1.1.

  1. 1.

The following implications of Theorem 2 are more-or-less obvious (see Lemma
7):

$\hbox{(\ref{equiv-isStrong})}\Rightarrow\vbox{\hbox{(\ref{equiv-hasNormal})}
\hbox to13.00005pt{\hss\rotatebox{90.0}{$\Leftarrow$}\hss} \hbox{(\ref{equiv-
hasStrong})}}\Rightarrow\hbox{(\ref{equiv-
hasCCA})}\Leftrightarrow\hbox{(\ref{equiv-
isCCA})}\Rightarrow\hbox{(\ref{equiv-notHam})}$

  2. 2.

The implication $(\ref{equiv-notHam}\Rightarrow\ref{equiv-isCCA})$ is also
known (but it is not obvious). It was proved by D. P. Byrne, M. J. Donner, and
T. Q. Sibley [2, cf. p. 324] for finite groups, and the general case was
established by E. Dobson, A. Hujdurović, K. Kutnar, and J. Morris [3, Thm.
2.3].

  3. 3.

For groups that are _finite,_ the implication $(\ref{equiv-
notHam}\Rightarrow\ref{equiv-hasNormal})$ was established by C. Wang, D. Wang,
and M. Xu [10]. The proof relies on the classification of finite groups that
do not have a Graphical Regular Representation (GRR), which is a difficult
theorem that was proved in a series of papers by several authors (see [6]).

Therefore, the implication $(\ref{equiv-hasStrong}\Rightarrow\ref{equiv-
isStrong})$ is the only new content of the theorem for finite groups, but
$(\ref{equiv-hasCCA}\Rightarrow\ref{equiv-hasStrong})$ is new for infinite
groups. Actually, we prove $(\ref{equiv-notHam}\Rightarrow\ref{equiv-
isStrong})$ (see Corollary 27), which contains both of these.

We also prove the following result (see Section 5), which was conjectured by
Byrne, Donner, and Sibley in [2, cf. p. 332]. It provides a direct proof of
$(\ref{equiv-isCCA}\Rightarrow\ref{equiv-isStrong})$.

######  Theorem 3.

If $G$ is any group, then every colour-permuting automorphism of the complete
graph $\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is
the composition of a group automorphism and a colour-preserving graph
automorphism.

As an offshoot of our proof of Theorem 3, we also establish the following
result (see Corollary!26), which shows that placing a natural restriction on
the colour-preserving automorphisms of a Cayley graph can also restrict the
colour-permuting automorphisms:

######  Proposition 4.

If every colour-preserving automorphism of $\operatorname{Cay}(G;S)$ is a
translation, then every colour-permuting automorphism of
$\operatorname{Cay}(G;S)$ is an affine map (i.e., $\operatorname{Cay}(G;S)$ is
strongly CCA).

######  Acknowledgments.

The authors thank Andrew Fiori for asking the question that inspired this
research: which groups have a Cayley graph that is strongly CCA? The first
author also thanks Joy Morris for financial support provided by a grant from
the Natural Science and Engineering Research Council of Canada
(RGPIN-2017-04905).

##  2 Preliminaries

Graphs in this paper are simple and undirected, but they may be infinite.

######  Notation 5.

  1. 1.

$G$ always denotes a group (which may be infinite).

  2. 2.

$\mathbf{1}$ is the identity element of $G$.

  3. 3.

$S$ (and $S^{\prime}$) always denotes an inverse-closed subset of $G$.

######  Remark 2.1.

In the statements of our results, it does not matter whether graphs are
allowed to have loops. This is because all of our results concern
automorphisms of Cayley graphs, and adding a loop to every vertex of a graph
does not affect its automorphism group.

###  2A Colour-permuting automorphisms

The following result collects several elementary observations about colour-
permuting automorphisms. All are trivial and/or well known.

######  Lemma 6.

  1. 1.

A permutation $\varphi$ of $G$ is a colour-preserving automorphism of
$\operatorname{Cay}(G;S)$ if and only if, for all $g\in G$ and $s\in S$, we
have $\varphi(gs)\in\\{\varphi(g)\,s^{\pm 1}\\}$. [8, p. 190]

  2. 2.

For each $g\in G$, the left translation $L_{g}\colon x\mapsto gx$ is a colour-
preserving automorphism of $\operatorname{Cay}(G;S)$. [8, p. 190]

  3. 3.

If $\alpha$ is an automorphism of the group $G$, such that
$\alpha(s)\in\\{s^{\pm 1}\\}$ for all $s\in S$, then $\alpha$ is a colour-
preserving automorphism of $\operatorname{Cay}(G;S)$. [8, p. 190]

  4. 4.

Every strongly CCA Cayley graph is CCA. So every strongly CCA group is CCA.
[8, p. 191]

  5. 5.

Every normal Cayley graph is strongly CCA. (cf. [8, Remark 6.2])

  6. 6.

Assume $S\subseteq S^{\prime}\subseteq G$. If $\operatorname{Cay}(G;S)$ is
CCA, then $\operatorname{Cay}(G;S^{\prime})$ is CCA. (cf. [5, Lemma. 3.1])

We now prove (or give references for) the easy parts of Theorem 2 that are
listed in Note 1.1(1).

######  Lemma 7.

  1. a.

$(\ref{equiv-hasNormal}\Rightarrow\ref{equiv-hasStrong})$ If either $G$ has a
Cayley graph that is normal, or $G\cong\mathbb{Z}_{4}\times\mathbb{Z}_{2}$,
then $G$ has a Cayley graph that is strongly CCA. (see 6(5) for the first
part)

  2. b.

$(\ref{equiv-isStrong}\Rightarrow\ref{equiv-hasStrong})$ If the complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is
strongly CCA, then $G$ has a Cayley graph that is strongly CCA.

  3. c.

$(\ref{equiv-hasStrong}\Rightarrow\ref{equiv-hasCCA})$ If $G$ has a Cayley
graph that is strongly CCA, then $G$ has a Cayley graph that is CCA. (see
6(4))

  4. d.

$(\ref{equiv-hasCCA}\Leftrightarrow\ref{equiv-isCCA})$ $G$ has a Cayley graph
that is CCA if and only if the complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is CCA.

  5. e.

$(\ref{equiv-isCCA}\Rightarrow\ref{equiv-notHam})$ If $G=Q_{8}\times B$, where
$b^{2}=\mathbf{1}$ for every $b\in B$, then the complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is not
CCA. [3, 1st paragraph of proof of Thm. 2.3] (or see Example 17(c))

######  Proof 2.2.

References have been provided for all but (b) and (d), and the fact (in (a))
that $\mathbb{Z}_{4}\times\mathbb{Z}_{2}$ has a Cayley graph that is strongly
CCA. The statement in (b) is completely trivial, so it requires no further
comment.

To establish the nontrivial direction $(\Rightarrow)$ of (d), note that if
$\operatorname{Cay}(G;S)$ is CCA, then we see from Lemma 6(6) that
$\operatorname{Cay}(G;G)$ is CCA, because $S\subseteq G$. Then the graph
obtained by removing the loop at every vertex is also CCA (see Remark 2.1), so
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is CCA.

It is easy to see that
$\operatorname{Cay}(\mathbb{Z}_{4}\times\mathbb{Z}_{2};S)$ is strongly CCA for
$S=\\{(\pm 1,0),(0,1)\\}$.

For completeness, we now establish a few additional well-known, elementary
facts.

######  Lemma 8.

Assume $\varphi$ is a colour-permuting automorphism of
$\operatorname{Cay}(G;S)$, $g\in G$, and $s,t\in S$. If
$\varphi(gs)=\varphi(g)\,t$, then $\varphi(gs^{n})=\varphi(g)\,t^{n}$ for all
$n\in\mathbb{Z}$.

######  Proof 2.3.

Since $\varphi$ is colour-permuting, we see that it is an isomorphism from
$\operatorname{Cay}\bigl{(}G;\\{s^{\pm 1}\\}\bigr{)}$ to
$\operatorname{Cay}\bigl{(}G;\\{t^{\pm 1}\\}\bigr{)}$. So it must restrict to
an isomorphism from the connected component of
$\operatorname{Cay}\bigl{(}G;\\{s^{\pm 1}\\}\bigr{)}$ that contains $g$ to the
connected component of $\operatorname{Cay}\bigl{(}G;\\{t^{\pm 1}\\}\bigr{)}$
that contains $\varphi(g)$. Since these components are cycles (except in the
trivial cases where they have only one or two vertices), the restriction of
$\varphi$ to this component is determined by what it does to a single edge.

######  Lemma 9.

Assume $\varphi$ is a colour-permuting automorphism of
$\operatorname{Cay}(G;S)$, such that $\varphi(\mathbf{1})=\mathbf{1}$. Then,
for all $g\in G$, $s\in S$, and $n\in\mathbb{Z}$, we have

$\varphi(gs^{n})\in\\{\varphi(g)\,\varphi(s)^{\pm n}\\}.$

######  Proof 2.4.

Fix $s\in S$. Since $\varphi$ is colour-permuting, there is some $t\in S$,
such that

$\varphi(gs)\in\\{\varphi(g)\,t^{\pm 1}\\}$ for all $g\in G$.

By taking $g=\mathbf{1}$, we see that $\varphi(s)\in\\{t^{\pm 1}\\}$.
Therefore $\varphi(gs)\in\\{\varphi(g)\,\varphi(s)^{\pm 1}\\}$ for all $g$.
The desired conclusion now follows from Lemma 8.

######  Lemma 10.

Assume $\varphi$ is a colour-permuting automorphism of
$\operatorname{Cay}(G;S)$, such that $\varphi(\mathbf{1})=\mathbf{1}$, and let
$H=\langle\,s\in S\mid s^{2}=\mathbf{1}\,\rangle$. Then
$\varphi(gh)=\varphi(g)\,\varphi(h)$ for all $g\in G$ and $h\in H$.

######  Proof 2.5.

Let $S_{2}$ be the set of all elements of order $2$ in $S$. Let $h\in H$, so
$h=s_{1}\dots s_{n}$ for some $s_{1},s_{2},\ldots,s_{n}\in S_{2}$.

Note that the elements of $S_{2}$ are precisely the elements of $S$ that
corresponding to undirected edges in $\operatorname{Cay}(G;S)$. Since
$\varphi$ is an automorphism (and $\varphi(\mathbf{1})=\mathbf{1}$), this
implies $\varphi(S_{2})=S_{2}$, so $\varphi(s)^{-1}=\varphi(s)$ for all $s\in
S_{2}$. Hence, we see from Lemma 9 (with $n=1$) that
$\varphi(gs_{i})=\varphi(g)\,\varphi(s_{i})$ for all $i$.

So

$\displaystyle\varphi(gh)$ $\displaystyle=\varphi(gs_{1}s_{2}\dots s_{n})$
$\displaystyle=\varphi(gs_{1}s_{2}\dots s_{n-1})\,\varphi(s_{n})$
$\displaystyle=\varphi(gs_{1}s_{2}\dots
s_{n-2})\,\varphi(s_{n-1})\,\varphi(s_{n})$ $\displaystyle\hskip
28.45274pt\vdots$
$\displaystyle=\varphi(g)\,\varphi(s_{1})\,\varphi(s_{2})\cdots\varphi(s_{n}).$

By taking $g=\mathbf{1}$, we see that

$\varphi(h)=\varphi(s_{1})\,\varphi(s_{2})\cdots\varphi(s_{n}).$

So $\varphi(gh)=\varphi(g)\,\varphi(h)$, as desired.

######  Lemma 11.

Assume $\varphi$ is a colour-preserving automorphism of
$\operatorname{Cay}(G;S)$, and let $H=\langle\,s\in S\mid
s^{2}=\mathbf{1}\,\rangle$. Then:

  1. 1.

$\varphi(xh)=\varphi(x)h$, for all $x\in G$ and $h\in H$.

  2. 2.

In particular, if $\varphi(\mathbf{1})=\mathbf{1}$, then $\varphi(h)=h$ for
all $h\in H$.

######  Proof 2.6.

This is very similar to the proof of Lemma 10.

Let $S_{2}$ be the set of all elements of order $2$ in $S$. Let $h\in H$, so
$h=s_{1}\dots s_{n}$ for some $s_{1},s_{2},\ldots,s_{n}\in S_{2}$. For all
$g\in G$, we have

$\varphi(gs_{i})\in\\{\varphi(g)\,s_{i}^{\pm 1}\\}=\\{\varphi(g)\,s_{i}\\},$

so

$\displaystyle\varphi(xh)$ $\displaystyle=\varphi(xs_{1}s_{2}\dots s_{n})$
$\displaystyle=\varphi(xs_{1}s_{2}\dots s_{n-1})s_{n}$
$\displaystyle=\varphi(xs_{1}s_{2}\dots s_{n-2})s_{n-1}s_{n}$
$\displaystyle\hskip 28.45274pt\vdots$
$\displaystyle=\varphi(x)s_{1}s_{2}\dots s_{n}$ $\displaystyle=\varphi(x)h.$

###  2B A few facts from group theory

######  Definition 12 (cf. [8, Definition 2.6]).

A group $G$ is of _dicyclic type_ if it has an abelian subgroup $A$ of index
$2$, an element $z$ of order $2$ that is in $A$, and an element $q\notin A$,
such that $q^{2}=z$, and every element of $A$ is inverted by $q$ (in the
action by conjugation). We write $G=\operatorname{Dic}(A,z,q)$.

######  Definition 13 ([12]).

A group $G$ is _hamiltonian_ if it is nonabelian, and every subgroup of $G$ is
normal. It can be shown that $G$ is hamiltonian if and only if it is
isomorphic to $Q_{8}\times A\times B$, for some abelian groups $A$ and $B$,
such that every element of $A$ has odd order, and every element of $B$ has
order $1$ or $2$.

######  Lemma 14.

If $H$ is a proper subgroup of a group $G$, then $\langle G\smallsetminus
H\rangle=G$, where $G\smallsetminus H=\\{\,g\in G\mid g\notin H\,\\}$.

######  Proof 2.7.

Since $G\smallsetminus H$ is obviously contained in $\langle G\smallsetminus
H\rangle$, it suffices to show that $H\subseteq\langle G\smallsetminus
H\rangle$. Since $H$ is proper, there is some $g\in G\smallsetminus H$. Then,
for any $h\in H$, we have $g^{-1}h\in G\smallsetminus H$, so

$h=g\,(g^{-1}h)\in(G\smallsetminus H)(G\smallsetminus H)\subseteq\langle
G\smallsetminus H\rangle.$

######  Lemma 15 (internal direct product [4, Theorem 9, p. 171]).

If $H$ and $K$ are normal subgroups of $G$, such that $HK=G$ and $H\cap
K=\\{\mathbf{1}\\}$, then $G$ is isomorphic to the direct product of $H$ and
$K$, and we write $G=H\times K$.

######  Lemma 16 (cf. [4, Proposition 14, p. 94]).

Assume $H$ and $K$ are subgroups of $G$. If $G=HK$, then $G=KH$.

##  3 Colour-preserving automorphisms of complete Cayley graphs

In this section, we recall a result that provides an explicit description of
all the colour-preserving automorphisms of any complete Cayley graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ (see
Theorem 18). It was proved by D. P. Byrne, M. J. Donner, and T. Q. Sibley [2,
p. 324] when $G$ is finite, and it was generalized to infinite groups by P.-H.
Leemann and M. de la Salle [9, Thm. 2]. This theorem will be needed in Section
4, so, for completeness, we provide a proof.

######  Example 17.

Here are some important (known) examples of colour-preserving automorphisms of
complete Cayley graphs.

  1. a.

Assume $G$ is abelian, and define $\iota\colon G\to G$ by $\iota(g)=g^{-1}$.
Then $\iota$ a colour-preserving automorphism of the complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ that
fixes $\mathbf{1}$. It is a group automorphism, and it is nontrivial if there
exists $g\in G$, such that $g^{2}\neq\mathbf{1}$.

  2. b.

Let $G=\operatorname{Dic}(A,z,q)$ be a (finite or infinite) group of dicyclic
type, and define $\varphi\colon G\to G$ by $\varphi(q^{i}a)=q^{-i}a$ for
$i\in\mathbb{Z}$ and $a\in A$. Then $\varphi$ is nontrivial colour-preserving
automorphism of the complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ that
fixes $\mathbf{1}$, and it is a group automorphism.

  3. c.

Let $G$ be a (finite or infinite) hamiltonian $2$-group, so $G=Q_{8}\times B$,
for some group $B$ of exponent dividing $2$. For every
$I\subseteq\\{i,j,k\\}$, there is a unique colour-preserving automorphism
$\varphi_{I}$ of the complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ that
fixes $\mathbf{1}$, and satisfies

$\text{for $\ell\in\\{i,j,k\\}$, \
$\varphi_{I}(\ell)=\ell\Leftrightarrow\ell\in I$}.$

Furthermore, $\varphi_{I}$ is a group automorphism if and only if $|I|$ is
odd.

There is some overlap between (b) and (c), because any hamiltonian $2$-group
is also a dicyclic group. For example, if we write $Q_{8}\times
B=\operatorname{Dic}\bigl{(}\langle k,B\rangle,i^{2},i\bigr{)}$, then the
automorphism described in (b) is equal to $\varphi_{\\{k\\}}$.

######  Proof 3.1.

All of these examples are included in the main theorem of [2], but the
notation and general presentation there are very different from ours, so we
provide brief justifications for the reader’s convenience.

It is easy to see (and well known) that if $\varphi$ is a group automorphism,
such that $\varphi(s)\in\\{s^{\pm 1}\\}$ for all $s\in S$, then $\varphi$ is a
colour-preserving automorphism of $\operatorname{Cay}(G;S)$ that fixes
$\mathbf{1}$.

(a) Note that $\iota$ is a group automorphism (because $G$ is abelian). Since
$\iota(g)=g^{-1}$ is obviously in $\\{g^{\pm 1}\\}$ for all $g\in G$, this
implies that $\iota$ is a colour-preserving automorphism of
$\operatorname{Cay}(G;S)$.

(b) For $a\in A$, we have $\varphi(a)=a$ and

$\varphi(qa)=q^{-1}a=a^{-1}q^{-1}=(qa)^{-1}.$

Therefore $\varphi(g)\in\\{g^{\pm 1}\\}$ for all $g\in G$.

Hence, all that remains is to show that $\varphi$ is a group automorphism. For
$b\in A$, we have

$\varphi\bigl{(}(q^{i}a)b\bigr{)}=\varphi\bigl{(}q^{i}(ab)\bigr{)}=q^{-i}ab=\varphi(q^{i}a)\,\varphi(b)$

and

$\varphi\bigl{(}(q^{i}a)(qb)\bigr{)}=\varphi\bigl{(}q^{i+1}(a^{-1}b)\bigr{)}=q^{-i-1}a^{-1}b=q^{-i}a\cdot
q^{-i}b=\varphi(q^{i}a)\,\varphi(qb).$

(c) The uniqueness follows from Lemma 11. So we only prove existence.

  1. 0.

Let $\varphi_{\emptyset}=\iota$, where $\iota(x)=x^{-1}$, as in (a). This is
not a group automorphism (because $G$ is not abelian).

However, we can easily show that it is a colour-preserving graph automorphism
(and it obviously fixes $\mathbf{1}$), by using an argument that is taken from
the first paragraph of the proof of [3, Theorem 2.3]. Let $g,s\in G$. Then
$\varphi_{\emptyset}(gs)=(gs)^{-1}=s^{-1}g^{-1}$. In $G=Q_{8}\times B$, every
element either inverts or commutes with every other element, so
$s^{-1}g^{-1}\in\\{g^{-1}s^{\pm 1}\\}=\\{\varphi(g)s^{\pm 1}\\}$.

  2. 1.

For $\ell\in\\{i,j,k\\}$, we may let $\varphi_{\\{\ell\\}}$ be the conjugation
by $\ell$. This is a group automorphism.

  3. 2.

If $|I|=2$, we have $I=\\{i,j,k\\}\smallsetminus\\{\ell\\}$, for some
$\ell\in\\{i,j,k\\}$. Then
$\varphi_{I}=\varphi_{\\{\ell\\}}\mathbin{\circ}\varphi_{\emptyset}$. This is
not a group automorphism, because it is the composition of an automorphism
with a non-automorphism.

  4. 3.

The automorphism $\varphi_{\\{i,j,k\\}}$ is the trivial permutation (i.e., the
identity map). This is a group automorphism.

######  Theorem 18 (Byrne-Donner-Sibley [2], Leemann and de la Salle [9, Thm.
2]).

Let $G$ be a (finite or infinite) group. If the complete Cayley graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ has a
nontrivial colour-preserving automorphism that fixes $\mathbf{1}$, then $G$ is
either abelian or dicyclic type. Furthermore, any such colour-preserving
automorphism is one of the automorphisms in Example 17.

######  Proof 3.2.

This is similar to the proof of [3, Thm. 2.3].

By assumption, we may let $\varphi$ be a nontrivial colour-preserving
automorphism of the complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ that
fixes $\mathbf{1}$. Let

$F=\\{\,f\in G\mid\varphi(f)=f\,\\},$

and let $F^{c}$ be the complement of $F$. Note that $F$ is a proper subset of
$G$, because $\varphi$ is nontrivial, and that

$\varphi(g)=g^{-1}$ for all $g\in F^{c}$

(because $\varphi$ is colour-preserving and fixes $\mathbf{1}$).

For all $f\in F$ and $h\in G$, such that $fh\in F^{c}$, we have

$\displaystyle\varphi(fh)$ $\displaystyle=(fh)^{-1}=h^{-1}f^{-1}$ and
$\displaystyle\varphi(fh)$ $\displaystyle\in\\{\varphi(f)h^{\pm
1}\\}=\\{fh^{\pm 1}\\}$

However, since $fh\notin F$, we know that $\varphi(fh)\neq fh$. So we must
have

$fh^{-1}=\varphi(fh)=h^{-1}f^{-1},$

which means that $h$ inverts $f$. Therefore $fh$ also inverts $f$. Thus, we
have shown:

$\displaystyle\text{every element of~{}$F^{c}$ inverts every element
of~{}$F$}.$ (3a)

Case 1 .  Assume $\varphi(x)=x^{-1}$ for all $x\in G$.  For all $g,h\in G$, we
have

$\displaystyle h^{-1}g^{-1}=(gh)^{-1}=\varphi(gh)\in\\{\varphi(g)h^{\pm
1}\\}=\\{g^{-1}h^{\pm 1}\\}\subseteq g^{-1}\langle h\rangle,$ (3b)

so $g$ normalizes $\langle h\rangle$. Since $g$ and $h$ are arbitrary elements
of $G$, this implies that every cyclic subgroup of $G$ is normal, from which
it follows that every subgroup of $G$ is normal. Therefore, $G$ is either
abelian or hamiltonian.

We may assume $G$ is hamiltonian, for otherwise $G$ and $\varphi$ are
described in Example 17(a). So $G=Q_{8}\times A\times B$, for some torsion
abelian group $A$ in which every element has odd order, and some group $B$ of
exponent dividing $2$ (see Definition 13).

We may assume $A$ is nontrivial, for otherwise $G$ and $\varphi$ are described
in Example 17(c) (with $\varphi=\iota=\varphi_{\emptyset}$). Now, let $a$ be a
nontrivial element of $A$. For $g,h\in G$, the calculation in (3b) shows that
$h^{-1}g^{-1}\in\\{g^{-1}h^{\pm 1}\\}$. By taking inverses, we conclude that
$gh\in\\{h^{\pm 1}g\\}$. Therefore, if $gh\neq hg$, then $gh=h^{-1}g$. Letting
$g=j$ and $h=ia$, we conclude that

$jia=gh=h^{-1}g=(i^{-1}a^{-1})j=jia^{-1},$

so $a=a^{-1}$. This contradicts the fact that every element of $A$ has odd
order.

######  Note.

Henceforth, we may assume that Case 3.2 does not apply, so there is some $x\in
G$, such that $\varphi(x)\neq x^{-1}$. Then $\varphi(x)=x$, so $x\in F$. Since
$\varphi(x)\neq x^{-1}$, we also see that $x\neq x^{-1}$. Hence, inverting the
elements of $F$ is not the same as centralizing the elements of $F$. So we
conclude from (3a) that $F$ contains its centralizer $C_{G}(F)$.

For any $q\in F^{c}$, we know that $q^{2}$ centralizes $F$ (because $q$
inverts $F$), so $q^{2}\in C_{G}(F)\subseteq F$. This implies that $q$ inverts
$q^{2}$. However, $q$ obviously centralizes $q^{2}$. So it must be the case
that $q^{-2}=q^{2}$, which means $|q^{2}|\in\\{1,2\\}$. However, we also know
from Lemma 11(2) that $|q|>2$, since $\varphi(q)\neq q$. So we conclude that
$|q^{2}|=2$. Thus:

$|q|=4$ for all $q\in F^{c}$. (3c)

Furthermore, for all $g,h\in F^{c}$, we know that $g$ and $h$ both invert $F$,
so $gh^{-1}\in C_{G}(F)$. This implies that all elements of $F^{c}$ are in the
same coset of $C_{G}(F)$:

$F^{c}\subseteq C_{G}(F)\,q\quad\text{for all $q\in F^{c}$}.$

Case 2 . Assume $F$ is a subgroup of $G$.  We will show that $G$ is of
dicyclic type, and $\varphi$ is the automorphism in Example 17(b).

Fix some $q\in F^{c}$.

  * •

Since $F^{c}\subseteq C_{G}(F)\,q\subseteq Fq$, we see that all elements of
$F^{c}$ are in the same coset of $F$. This means $|G:F|=2$.

  * •

Since $q$ inverts $F$, and conjugation by $q$ is an automorphism, we see that
inversion is an automorphism of $F$. This implies that $F$ is abelian.

  * •

Let $z=q^{2}$. We know from the above note that $|q|=4$, so $|z|=2$.

We have now established that $G=\operatorname{Dic}(F,z,q)$.

So it only remains to show that $\varphi(q^{i}f)=q^{-i}f$ for all
$i\in\mathbb{Z}$ and $f\in F$.

  * •

If $i$ is even, then $q^{i}f\in F$, so $\varphi(q^{i}f)=q^{i}f$. However,
since $i$ is even and $|q|=4$, we also have $q^{i}=q^{-i}$.

  * •

If $i$ is odd, then $q^{i}f\in F^{c}$, so

$\varphi(q^{i}f)=(q^{i}f)^{-1}=f^{-1}q^{-i}=q^{-i}f,$

since $q$ inverts every element of $f$ (and $i$ is odd).

Case 3 . Assume $F$ is not a subgroup of $G$.  For convenience, let
$C=C_{G}(F)$ be the centralizer of $F$. As mentioned in the above note, we
have $C\subseteq F$, and we have $F^{c}\subseteq Cq$ for every $q\in F^{c}$.

Since $F^{c}\subseteq Cq$, we know that $F$ contains all of the cosets of $C$
except $Cq$. Also, since $F$ is not a subgroup, we know that $\langle
F\rangle$ is strictly larger than $F$, which means it contains some element of
$F^{c}$, and therefore contains some element of $Cq$. Since $C\subseteq F$,
this implies that $\langle F\rangle$ contains $Cq$. It also contains $F$, so
it contains all of the other cosets of $C$, as well. Therefore $\langle
F\rangle=G$. This implies that $C$ is the centre of $G$.

Thus, all elements of $F^{c}$ are in the same coset of the centre, so

$\text{the elements of~{}$F^{c}$ commute with each other}.$

Also recall (see (3a)) that

$\text{every element of~{}$F^{c}$ inverts every element of~{}$F$}.$

Now, let $f_{1},f_{2}\in F$. If $f_{1}f_{2}\notin F$, then it inverts both
$f_{1}$ and $f_{2}$, which implies that $f_{1}$ inverts $f_{2}$ and $f_{2}$
inverts $f_{1}$. On the other hand, if $f_{1}f_{2}\in F$, then the conjugation
action of any element of $F^{c}$ respects multiplication, but inverts $f_{1}$,
$f_{2}$, and $f_{1}f_{2}$, so we must have $f_{1}f_{2}=f_{2}f_{1}$. Therefore,
if $f_{1}$ and $f_{2}$ are any elements of $F$, then

$\text{either $f_{1}$ and~{}$f_{2}$ commute, or they invert each other}.$

Now consider any $f\in F$, such that $f\notin C$. Then $qf\notin qC$, so
$qf\notin F^{c}$. This means $qf\in F$, so

$qf=\varphi(qf)\in\\{\varphi(q)\,f^{\pm 1}\\}=\\{q^{-1}\,f^{\pm 1}\\},$

so $q^{2}\in\\{\mathbf{1},f^{-2}\\}$. However, we know from (3c) that $|q|=4$,
so $q^{2}\neq\mathbf{1}$. So we conclude that

$\displaystyle q^{2}=f^{-2}.$ (3d)

Therefore (recalling that $q$ inverts $f$) we have

$f^{-1}qf=f^{-2}q=q^{2}\,q=q^{3}\in\langle q\rangle.$

So $f$ normalizes $\langle q\rangle$. Since this is also clearly true for the
elements of $F$ that are in $C$, we conclude that

if $f\in F$ and $q\in F^{c}$, then $f$ normalizes $\langle q\rangle$.

We have now shown that $g$ normalizes $\langle h\rangle$ for all $g,h\in G$.
This means that every cyclic subgroup of $G$ is normal. It follows easily that
every subgroup of $G$ is normal. (Also, $G$ is not abelian, because elements
of $F^{c}$ invert elements of $F$.) Therefore $G$ is a hamiltonian group (see
Definition 13).

We claim that $G$ is a 2-group. To see this, write $G=Q_{8}\times A\times B$,
as in Definition 13. We wish to show that $A$ is trivial. Suppose not. Then,
since $F$ contains all but one coset of the centre, there is some $f\in F$,
such that $f\notin C$, and the $A$-component of $f$ is nontrivial. From (3d)
we know that $|f^{2}|=2$, which contradicts the fact that the $A$-component of
$f^{2}$ is nontrivial.

All elements of the centre $C$ of $G$ have order $2$. Therefore, since
$\varphi(q)=q^{-1}$ (and $\varphi$ is colour-preserving), we have
$\varphi(qc)=\varphi(q)c^{\pm 1}=q^{-1}c=(qc)^{-1}$ for all $c\in C$. So
$F^{c}$ is the entire coset $qC$. Hence, $F^{c}$ contains some
$\ell\in\\{i,j,k\\}$. Then it is easy to see that $\varphi$ is the permutation
$\varphi_{I}$ defined in Example 17(c), where
$I=\\{i,j,k\\}\smallsetminus\\{\ell\\}$.

The above theorem provides another proof of the (known) implication
$(\ref{equiv-notHam}\Rightarrow\ref{equiv-isCCA})$ of Theorem 2, which was
discussed in Note 1.1(2) of the introduction:

######  Corollary 19 (Byrne et al. [2, cf. p. 324], Dobson et al. [3, Thm.
2.3]).

If the complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is not
CCA, then $G$ is a hamiltonian $2$-group.

######  Proof 3.3.

Since $\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is
not CCA, there exists a colour-preserving automorphism $\varphi$ of this
complete Cayley graph, such that $\varphi$ is not affine. After composing with
a translation, we may assume $\varphi(\mathbf{1})=\mathbf{1}$. Since $\varphi$
is not affine, it is obviously not trivial, so Theorem 18 tells us that $G$ is
abelian or dicyclic, and that $\varphi$ is one of the automorphisms in Example
17. However, since $\varphi$ is not affine, it is not a group automorphism, so
it is not listed in part (a) or (b) of that example. Hence, it must be part
(c) that applies, so $G$ is a hamiltonian $2$-group.

##  4 Complete graphs that are not strongly CCA

######  Notation 20.

Let $X=\operatorname{Cay}(G;S)$ be a Cayley graph of $G$.

  1. 1.

$\mathcal{A}(X)$ is the group of all colour-permuting automorphisms of $X$.

  2. 2.

$\mathcal{A}^{0}(X)$ is the group of all colour-preserving automorphisms of
$X$.

  3. 3.

$\mathcal{A}_{\mathbf{1}}(X)$ and $\mathcal{A}^{0}_{\mathbf{1}}(X)$ are the
stabilizers of the vertex $\mathbf{1}$ in $\mathcal{A}(X)$ and
$\mathcal{A}^{0}(X)$, respectively.

  4. 4.

For $\varphi\in\mathcal{A}(X)$, and $g\in G$, let $\pi^{\varphi}_{g}$ be the
permutation of $S$ that is induced by $\varphi$ at the vertex $g$. That is,
for all $s\in S$, we have

$\varphi(gs)=\varphi(g)\,\pi^{\varphi}_{g}(s).$

  5. 5.

For $\varphi\in\mathcal{A}(X)$, let $\overline{\pi}^{\varphi}$ be the
permutation of the colours that is induced by $\varphi$. Thus, for all $g\in
G$ and $s\in S$, we have

$\overline{\pi}^{\varphi}(\\{s^{\pm 1}\\})=\\{\pi^{\varphi}_{g}(s)^{\pm
1}\\}.$

  6. 6.

For $g\in G$, let $L_{g}$ be the left-translation by $g$, so $L_{g}(x)=gx$ for
all $x\in G$. This is a colour-preserving automorphism of every Cayley graph
of $G$.

We have the following elementary (and well-known) observation:

######  Lemma 21.

For $\varphi\in\mathcal{A}_{\mathbf{1}}(X)$, we have
$\varphi\in\operatorname{Aut}G$ if and only if
$\pi^{\varphi}_{g}=\pi^{\varphi}_{h}$ for all $g,h\in G$.

######  Lemma 22.

Given $\varphi\in\mathcal{A}_{\mathbf{1}}(X)$, $g\in G$, and $s\in S$, let

$\psi=L_{g}^{-1}\,\varphi^{-1}\,L_{\varphi(g)}\,L_{\varphi(gs)}^{-1}\,\varphi\,L_{gs}.$

Then $\psi\in\mathcal{A}^{0}_{\mathbf{1}}(X)$ and $\psi(s)=s$.

######  Proof 4.1.

It is clear that $\psi$ is colour-permuting, because it is a composition of
colour-permuting automorphisms. Furthermore, letting $\operatorname{id}$
denote a trivial permutation, we have

$\displaystyle\overline{\pi}^{\psi}$
$\displaystyle=\overline{\pi}^{L_{g}^{-1}}\mathbin{\circ}\overline{\pi}^{\varphi^{-1}}\mathbin{\circ}\overline{\pi}^{L_{\varphi(g)}}\mathbin{\circ}\overline{\pi}^{L_{\varphi(gs)}^{-1}}\mathbin{\circ}\overline{\pi}^{\varphi}\mathbin{\circ}\overline{\pi}^{L_{gs}}$
$\displaystyle=\operatorname{id}\mathbin{\circ}\overline{\pi}^{\varphi^{-1}}\mathbin{\circ}\operatorname{id}\mathbin{\circ}\operatorname{id}\mathbin{\circ}\overline{\pi}^{\varphi}\mathbin{\circ}\operatorname{id}$
$\displaystyle\begin{pmatrix}\text{translations are}\\\ \text{colour-
preserving}\end{pmatrix}$ $\displaystyle=\overline{\pi}^{\varphi^{-1}\varphi}$
$\displaystyle=\overline{\pi}^{\operatorname{id}}$
$\displaystyle=\operatorname{id}.$

So the colour-permuting automorphism $\psi$ is actually colour-preserving.

Also, a straightforward calculation shows that $\psi(\mathbf{1})=\mathbf{1}$.
Therefore $\psi\in\mathcal{A}^{0}_{\mathbf{1}}(X)$.

Furthermore,

$\displaystyle\psi(s^{-1})$
$\displaystyle=L_{g}^{-1}\,\varphi^{-1}\,L_{\varphi(g)}\,L_{\varphi(gs)}^{-1}\,\varphi\,L_{gs}(s^{-1})$
$\displaystyle=L_{g}^{-1}\,\varphi^{-1}\,L_{\varphi(g)}\,L_{\varphi(gs)}^{-1}\,\varphi(g)$
$\displaystyle=L_{g}^{-1}\,\varphi^{-1}\,L_{\varphi(g)}\bigl{(}\varphi(gs)^{-1}\,\varphi(g)\bigr{)}$
$\displaystyle=L_{g}^{-1}\,\varphi^{-1}\,L_{\varphi(g)}\bigl{(}\pi^{\varphi}_{g}(s)^{-1}\bigr{)}$
$\displaystyle=L_{g}^{-1}\,\varphi^{-1}\,L_{\varphi(g)}\bigl{(}\pi^{\varphi}_{g}(s^{-1})\bigr{)}$
(Lemma 8 with $g=\mathbf{1}$ and $n=-1$)
$\displaystyle=L_{g}^{-1}\,\varphi^{-1}\bigl{(}\varphi(gs^{-1})\bigr{)}$
$\displaystyle=L_{g}^{-1}(gs^{-1})$ $\displaystyle=s^{-1}.$

Now, it follows from Lemma 8 (with $g=\mathbf{1}$ and $n=-1$) that
$\psi(s)=s$.

######  Lemma 23.

Let $X=\operatorname{Cay}(G;S)$ be a Cayley graph of $G$, and let

$S^{*}=\bigl{\\{}s\in S\mid\text{no nontrivial element of
$\mathcal{A}^{0}_{\mathbf{1}}(X)$ fixes~{}$s$}\bigr{\\}}.$

If $S^{*}$ generates $G$, then $X$ is strongly CCA.

######  Proof 4.2.

Given $\varphi\in\mathcal{A}_{\mathbf{1}}(X)$, we wish to show that
$\varphi\in\operatorname{Aut}G$. Fix some $g\in G$ and $s\in S^{*}$, and, as
in Lemma 22, let

$\psi=L_{g}^{-1}\,\varphi^{-1}\,L_{\varphi(g)}\,L_{\varphi(gs)}^{-1}\,\varphi\,L_{gs}.$

so $\psi\in\mathcal{A}^{0}_{\mathbf{1}}(X)$ and $\psi(s)=s$. Since $s\in
S^{*}$, it follows from the definition of $S^{*}$ that $\psi$ is the identity
map. Thus, for all $t\in S$, we have $\psi(t)=t$, so, by the definition of
$\psi$, we have

$L_{\varphi(g)}^{-1}\varphi L_{g}(t)=L_{\varphi(gs)}^{-1}\varphi L_{gs}(t),$

which means $\pi^{\varphi}_{g}(t)=\pi^{\varphi}_{gs}(t)$. Therefore
$\pi^{\varphi}_{g}=\pi^{\varphi}_{gs}$. Since $s$ is an arbitrary element of
$S^{*}$ and $S^{*}$ generates $G$, repeated application of this fact implies
that $\pi^{\varphi}_{g}=\pi^{\varphi}_{h}$ for all $g,h\in G$. Therefore
$\varphi\in\operatorname{Aut}(G)$ (see Lemma 21).

######  Definition 24 ([11, p. 8]).

A permutation group is _semiregular_ if no nonidentity element of the group
has any fixed points.

######  Corollary 25.

Let $X=\operatorname{Cay}(G;S)$ be a connected Cayley graph of $G$. If the
action of $\mathcal{A}^{0}_{\mathbf{1}}(X)$ on $S$ is semiregular, then $X$ is
strongly CCA.

######  Proof 4.3.

In this case, we have $S^{*}=S$. Since $X$ is connected, we know that $S$
generates $G$.

######  Corollary 26.

Let $X=\operatorname{Cay}(G;S)$ be a Cayley graph of $G$. If
$\mathcal{A}^{0}_{\mathbf{1}}(X)$ is trivial, then $X$ is strongly CCA.

######  Proof 4.4.

Any trivial permutation group is obviously semiregular, so this is almost
immediate from Corollary 25. The only issue (which is minor) is that the
corollary requires $X$ to be connected. However, it is easy to see that if
$\mathcal{A}^{0}_{\mathbf{1}}(X)$ is trivial, then either $X$ is connected, or
$X$ has only two vertices.

We can now establish the implication $(\ref{equiv-
notHam}\Rightarrow\ref{equiv-isStrong})$ of Theorem 2.

######  Corollary 27.

If $G$ is not a hamiltonian $2$-group, then
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is
strongly CCA.

######  Proof 4.5.

In the notation of Lemma 23, it suffices to show that $\langle
S^{*}\rangle=G$.

To this end, let $\varphi$ be a nontrivial element of
$\mathcal{A}^{0}_{\mathbf{1}}(X)$. By Theorem 18 (and the assumption that $G$
is not a hamiltonian $2$-group), $\varphi$ must be described in (a) or (b) of
Example 17. Since each of these parts describes a unique automorphism, this
implies that $\varphi$ is the only nontrivial element of
$\mathcal{A}^{0}_{\mathbf{1}}(X)$. (Also note that
$S=G\smallsetminus\\{\mathbf{1}\\}$ in the complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$).)
Therefore, we have

$\text{$S^{*}=G\smallsetminus F$, where $F=\\{\,g\in
G\mid\varphi(g)=g\,\\}$}.$

Since $\varphi$ is nontrivial, we know that $F$ is a proper subset of $G$.
Also, in both (a) and (b) of Example 17, it is easy to see that $F$ is a
subgroup of $G$. (In (a), it is the subgroup $\\{\,x\in G\mid
x^{2}=\mathbf{1}\,\\}$; in (b), it is the subgroup $A$.) Therefore, it is
immediate from Lemma 14 that $\langle S^{*}\rangle=G$.

##  5 Colour-permuting automorphisms of complete Cayley graphs

In this section, we prove Theorem 3. For the reader’s convenience, we state
the result again here:

######  Theorem 3.

If $G$ is any (finite or infinite) group, then every colour-permuting
automorphism of the complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is the
composition of a group automorphism and a colour-preserving graph
automorphism.

In other words (and in the notation of Notation 20), we prove:

$\mathcal{A}\bigl{(}\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}\bigr{)}=\operatorname{Aut}(G)\cdot\mathcal{A}^{0}\bigl{(}\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}\bigr{)}.$

(Note that the order of the factors on the right-hand side does not matter: if
$H$ and $K$ are subgroups of $G$, such that $G=HK$, then also $G=KH$ (see
Lemma 16).

######  Proof 5.1 (Proof of Theorem 3).

Let
$K_{G}=\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$,
and let $\varphi$ be a colour-permuting automorphism of $K_{G}$. We wish to
show that $\varphi$ is the composition of a group automorphism and a colour-
preserving graph automorphism. By composing $\varphi$ with a translation, we
may assume, without loss of generality, that $\varphi(\mathbf{1})=\mathbf{1}$.

If $K_{G}$ is strongly CCA, then $\varphi$ must be a group automorphism. So
the desired conclusion is true in this case.

We may now assume that $K_{G}$ is not strongly CCA. By the contrapositive of
Corollary 27, this implies that $G$ is a hamiltonian $2$-group:

$G=Q_{8}\times B,$

for some abelian group $B$ of exponent $\leq 2$. Let $G_{2}=\langle
i^{2},B\rangle$ be the subgroup generated by the elements of order $2$ in $G$.
(Recall that $i^{2}=j^{2}=k^{2}$ is the unique element of order $2$ in
$Q_{8}$.) This is the centre of $G$, and it is an abelian group of exponent
$2$ that has index $4$ in $G$. By Lemma 10, we have

$\varphi(gx)=\varphi(g)\,\varphi(x)$ for all $g\in G$ and $x\in G_{2}$.

Therefore

$\varphi(G_{2})=G_{2}$, and the restriction of $\varphi$ to $G_{2}$ is a group
automorphism. (5e)

Note that $\operatorname{Cay}\bigl{(}G;\\{i^{\pm 1}\\}\bigr{)}$ is a disjoint
union of $4$-cycles (because $i$ has order $4$). Hence, the isomorphic graph
$\operatorname{Cay}\bigl{(}G;\\{\varphi(i)^{\pm 1}\\}\bigr{)}$ is also a
disjoint union of $4$-cycles, which means that $\varphi(i)$ has order $4$.
Therefore $\varphi(i)^{\pm 2}=i^{2}$, because $g^{2}=i^{2}$ for all $g\in G$
of order 4. Also, we have $\varphi(i^{2})\in\\{\varphi(i)^{\pm 2}\\}$ (see
Lemma 8). Combining these observations yields

$\varphi(i^{2})=i^{2}.$

Now, let $\widetilde{Q}_{8}=\langle\varphi(i),\varphi(j)\rangle$, and define
$\alpha\colon Q_{8}\to G$ by

$\alpha(i^{m}j^{n})=\varphi(i)^{m}\,\varphi(j)^{n}.$

(We will soon see that $\alpha$ is well-defined.) Since $i$ and $j$ have order
$4$ (and $\varphi\in\mathcal{A}_{\mathbf{1}}(K_{G})$), we know that
$\varphi(i)$ and $\varphi(j)$ have order $4$ (by the argument in the preceding
paragraph). Also note that $i\notin j\,G_{2}$, so (5e) implies that
$\varphi(i)\notin\varphi(j)\,G_{2}$; hence, $\varphi(i)$ does not centralize
$\varphi(j)$. However, any two elements of $G$ either commute or invert each
other; therefore $\varphi(i)$ and $\varphi(j)$ invert each other, so
$\varphi(i)$ and $\varphi(j)$ satisfy exactly the same relations as $i$ and
$j$. We conclude that

$\alpha$ is a (well-defined) isomorphism from $Q_{8}$ to $\widetilde{Q}_{8}$.
(5f)

Also note that, for all $m,n\in\mathbb{Z}$, Lemma 9 implies

$\varphi(i^{m}j^{n})\in\\{\varphi(i^{m})\,\varphi(j)^{\pm
n}\\}\subseteq\\{\varphi(i)^{\pm m}\,\varphi(j)^{\pm
n}\\}\subseteq\alpha(Q_{8})=\widetilde{Q}_{8},$

so $\varphi(Q_{8})=\widetilde{Q}_{8}$. Therefore, since $Q_{8}\cap
G_{2}=\langle i^{2}\rangle$, we see that

$\widetilde{Q}_{8}\cap\varphi(G_{2})=\varphi(Q_{8})\cap\varphi(G_{2})=\varphi(Q_{8}\cap
G_{2})=\varphi\bigl{(}\langle i^{2}\rangle\bigr{)}=\langle i^{2}\rangle.$

Since $\varphi(B)\subseteq\varphi(G_{2})$ and $i^{2}\notin B$, this implies
$\widetilde{Q}_{8}\cap\varphi(B)=\\{\mathbf{1}\\}$. Also, since the
restriction of $\varphi$ to $G_{2}$ is a group automorphism, we know that
$\varphi(B)$ is a subgroup of $G$ and we have $|G:\varphi(B)|=|G:B|=8$; from
this, we can conclude that $\widetilde{Q}_{8}\cdot\varphi(B)=G$. So we see
from Lemma 15 that

$\displaystyle G=\widetilde{Q}_{8}\times\varphi(B).$ (5g)

Define $\beta\colon G\to G$ by

$\beta(gb)=\alpha(g)\,\varphi(b)$ for $g\in Q_{8}$ and $b\in B$.

We see from (5e), (5f), and (5g) that $\beta$ is an automorphism of $G$.

Now, let $\psi=\beta^{-1}\mathbin{\circ}\varphi$. To complete the proof, we
will show that $\psi$ is a colour-preserving automorphism of
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$. (This
implies that, as desired, $\varphi=\beta\mathbin{\circ}\psi$ is the
composition of a group automorphism, namely $\beta$, and a colour-preserving
graph automorphism, namely $\psi$.) First, note that $\psi$ is a colour-
permuting automorphism (because it is the composition of two colour-permuting
automorphisms) and that $\psi(\mathbf{1})=\mathbf{1}$ (because $\beta$ and
$\varphi$ both fix $\mathbf{1}$).

If $m,n\in\mathbb{Z}$, and $n$ is odd, then conjugation by $j^{n}$ inverts
$i^{m}$, so

$i^{m}j^{-n}=j^{-n}\cdot(j^{n}i^{m}j^{-n})=j^{-n}\cdot
i^{-m}=(i^{m}j^{n})^{-1}.$

On the other hand, if $n$ is even, then $j^{-n}=j^{n}$, so
$i^{m}j^{-n}=i^{n}j^{n}$. Thus, we have

$\displaystyle\text{$i^{m}j^{-n}\in\\{(i^{m}j^{n})^{\pm 1}\\}$ for all
$m,n\in\mathbb{Z}$}.$ (5h)

Hence, for all $q\in Q_{8}$, we have

$\displaystyle\varphi(q)$ $\displaystyle=\varphi(i^{m}j^{n})$ (for some
$m,n\in\mathbb{Z}$) $\displaystyle\in\\{\varphi(i^{m})\,\varphi(j)^{\pm n}\\}$
(Lemma 9) $\displaystyle=\\{\varphi(i)^{m}\,\varphi(j)^{\pm n}\\}$ (Lemma 8
with $g=\mathbf{1}$) $\displaystyle=\\{\beta(i)^{m}\,\beta(j)^{\pm n}\\}$
(definitions of $\beta$ and $\alpha$) $\displaystyle=\\{\beta(i^{m}j^{\pm
n})\\}$ ($\beta$ is a group homomorphism)
$\displaystyle\subseteq\bigl{\\{}\beta\bigl{(}(i^{m}j^{n})^{\pm
1}\bigr{)}\bigr{\\}}$ ((5h) $\displaystyle=\\{\beta(q^{\pm 1})\\}$ (definition
of $m$ and $n$) $\displaystyle=\\{\beta(q)^{\pm 1}\\}$
$\displaystyle\text{($\beta$ is a group homomorphism)}.$

Therefore

$\displaystyle\text{$\beta(q)\in\\{\varphi(q)^{\pm 1}\\}$ for all $q\in
Q_{8}$}.$ (5i)

Now, for any $s\in G$, we have

$\displaystyle\beta(s)$ $\displaystyle=\beta(qb)$ (for some $q\in Q_{8}$ and
$b\in B$) $\displaystyle=\beta(q)\,\beta(b)$ ($\beta$ is a group automorphism)
$\displaystyle\in\\{\varphi(q)^{\pm 1}\,\beta(b)\\}$ (5i)
$\displaystyle=\\{\bigl{(}\varphi(q)\,\beta(b)\bigr{)}^{\pm 1}\\}$
$\displaystyle\begin{pmatrix}\text{$\beta(b)\in G_{2}$ has order~{}$1$
or~{}$2$}\\\ \text{and is in the centre of~{}$G$}\end{pmatrix}$
$\displaystyle=\\{\bigl{(}\varphi(q)\,\varphi(b)\bigr{)}^{\pm 1}\\}$
(definitions of $\beta$ and $\alpha$) $\displaystyle=\\{\varphi(qb)^{\pm
1}\\}$ (Lemma 10) $\displaystyle=\\{\varphi(s)^{\pm 1}\\}$
$\displaystyle\text{(definition of $q$ and $b$)}.$

Since $\varphi(s^{-1})=\varphi(s)^{-1}$ (by Lemma 8 with $g=\mathbf{1}$) and
$\beta(s^{-1})=\beta(s)^{-1}$ (because $\beta$ is a group homomorphism), this
implies

$\text{$\varphi\bigl{(}\\{s^{\pm 1}\\}\bigr{)}=\beta\bigl{(}\\{s^{\pm
1}\\}\bigr{)}$ for all $s\in G$}.$

Therefore, we have

$\psi\bigl{(}\\{s^{\pm
1}\\}\bigr{)}=\beta^{-1}\bigl{(}\varphi\bigl{(}\\{s^{\pm
1}\\}\bigr{)}\bigr{)}=\beta^{-1}\bigl{(}\beta\bigl{(}\\{s^{\pm
1}\\}\bigr{)}\bigr{)}=\\{s^{\pm 1}\\}.$

Hence, for all $g,s\in G$, we see from Lemma 9 that

$\psi(gs)\in\\{\psi(g)\,\psi(s^{\pm 1})\\}=\\{\psi(g)\,s^{\pm 1}\\}.$

This means that $\psi$ is colour-preserving, as desired.

This theorem yields a direct proof of the implication $(\ref{equiv-
isCCA}\Rightarrow\ref{equiv-isStrong})$ of Theorem 2:

######  Corollary 29.

If the complete graph
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is CCA,
then it is strongly CCA.

######  Proof 5.2.

Let $\varphi$ be a colour-permuting automorphism of
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$. By
Theorem 3, we may write $\varphi=\psi\mathbin{\circ}\alpha$, where $\psi$ is a
colour-preserving graph automorphism and $\alpha\in\operatorname{Aut}G$.
However, since
$\operatorname{Cay}\bigl{(}G;G\smallsetminus\\{\mathbf{1}\\}\bigr{)}$ is CCA,
we know that $\psi$ is an affine map. Hence, $\varphi$ is the composition of
two affine maps, and is therefore affine.

## References

  * [1] A. S. Árnadóttir and C. Godsil, Strongly cospectral vertices in normal Cayley graphs. _Discrete Math._ 346 (2023), no. 5, Paper No. 113341, 17 pp. MR4543505, https://doi.org/10.1016/j.disc.2023.113341
  * [2] D. P. Byrne, M. J. Donner, and T. Q. Sibley, Groups of graphs of groups. _Beitr. Algebra Geom._ 54 (2013), no. 1, 323–332. MR3027684, https://doi.org/10.1007/s13366-012-0093-7
  * [3] E. Dobson, A. Hujdurović, K. Kutnar, and J. Morris, On color-preserving automorphisms of Cayley graphs of odd square-free order. _J. Algebraic Combin._ 45 (2017), no. 2, 407–422. MR3604062, https://doi.org/10.1007/s10801-016-0711-9
  * [4] D. S. Dummit and M. Foote, _Abstract Algebra_ , third ed., John Wiley & Sons, Hoboken, NJ, 2004. MR2286236, ISBN: 0-471-43334-9
  * [5] B. Fuller, Finding CCA groups and graphs algorithmically. Masters thesis, University of Lethbridge, 2018. https://hdl.handle.net/10133/4996
  * [6] C. D. Godsil, GRRs for nonsolvable groups, in: _Algebraic Methods in Graph Theory, Vol. I, II (Szeged, 1978)_ , North-Holland Publishing Co., Amsterdam-New York, 1981, pp. 221–239. MR0642043, ISBN: 0-444-85442-8
  * [7] C. D. Godsil, On the full automorphism group of a graph. _Combinatorica_ 1 (1981), no. 3, 243–256. MR0637829, https://doi.org/10.1007/BF02579330
  * [8] A. Hujdurović, K. Kutnar, D. W. Morris, and J. Morris, On colour-preserving automorphisms of Cayley graphs. _Ars. Math. Contemp._ 11 (2016), no. 1, 189–213. MR3546658, https://doi.org/10.26493/1855-3974.771.9b3
  * [9] P.-H. Leemann and M. de la Salle, Most rigid representation and Cayley index of finitely generated groups. _Electron. J. Combin._ 29 (2022), no. 4, Paper No. 4.40, 9 pp. MR4522312, https://doi.org/10.37236/10512
  * [10] C. Wang, D. Wang, and M. Xu, Normal Cayley graphs of finite groups. _Sci. China Ser. A_ 41 (1998), no. 3, 242–251. MR1621054, https://doi.org/10.1007/BF02879042
  * [11] H. Wielandt, _Finite Permutation Groups_ , Academic Press, New York-London, 1964. MR0183775, ISBN:978-0-12-749650-4
  * [12] Wikipedia, Dedekind group. https://en.wikipedia.org/wiki/Dedekind_group