ARS MATHEMATICA CONTEMPORANEA 11 (2016) 189–213

## On colour-preserving automorphisms of Cayley graphs

### Ademir Hujdurovi´c

^{∗},

### Klavdija Kutnar

^{†}

University of Primorska, FAMNIT, Glagoljaˇska 8, 6000 Koper, Slovenia

### Dave Witte Morris

,### Joy Morris

^{‡}

Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Alberta, T1K 3M4, Canada

Received 25 November 2014, accepted 26 March 2015, published online 20 October 2015

Abstract

We study the automorphisms of a Cayley graph that preserve its natural edge-colouring.

More precisely, we are interested in groupsG, such that every such automorphism of every connected Cayley graph onGhas a very simple form: the composition of a left-translation and a group automorphism. We find classes of groups that have the property, and we determine the orders of all groups that do not have the property. We also have analogous results for automorphisms that permute the colours, rather than preserving them.

Keywords: Cayley graph, automorphism, colour-preserving, colour-permuting.

Math. Subj. Class.: 05C25

### 1 Introduction

Definitions 1.1. LetSbe a subset of a groupG, such thatS =S^{−1}. (All groups and all
graphs in this paper are finite.)

• TheCayley graphofG, with respect toS, is the graphCay(G;S)whose vertices are the elements ofG, and with an edgex xs, for eachx∈Gands∈S.

∗Partially supported by the Slovenian Research Agency: research program P1-0285.

†Partially supported by the Slovenian Research Agency: research program P1-0285 and research projects N1-0011, J1-6743, and J1-6720.

‡Partially supported by a research grant from the Natural Sciences and Engineering Research Council of Canada.

E-mail addresses:ademir.hujdurovic@upr.si (Ademir Hujdurovi´c), klavdija.kutnar@upr.si (Klavdija Kutnar), dave.morris@uleth.ca (Dave Witte Morris), joy.morris@uleth.ca (Joy Morris)

cbThis work is licensed under http://creativecommons.org/licenses/by/3.0/

• Cay(G;S)has a natural edge-colouring. Namely, each edge of the formx xsis
coloured with the set{s, s^{−1}}. (In order to make the colouring well-defined, it is
necessary to includes^{−1}, becausex xsis the same as the edgexs x, which is
of the formy ys^{−1}, withy =xs.)

Note thatCay(G;S)is connected if and only ifS generatesG. Also note that a permu- tationϕofGis a colour-preserving automorphism ofCay(G;S)if and only if we have ϕ(xs)∈

ϕ(x)s^{±}^{1} , for eachx∈Gands∈S.

For anyg ∈ G, the left translationx 7→ gxis a colour-preserving automorphism of
Cay(G;S). In addition, ifαis an automorphism of the groupG, such thatα(s)∈ {s^{±}^{1}}
for alls∈S, thenαis also a colour-preserving automorphism ofCay(G;S). We will see
that, in many cases, every colour-preserving automorphism ofCay(G;S)is obtained by
composing examples of these two obvious types.

Definition 1.2. LetGbe a group.

1. A functionϕ:G→Gis said to beaffineif it is the composition of an automorphism ofGwith left translation by an element ofG. This meansϕ(x) =α(gx), for some α∈AutGandg∈G.

2. A Cayley graphCay(G;S)isCCAif all of its colour-preserving automorphisms are affine functions onG. (CCA is an abbreviation for theCayley Colour Automorphism property.)

3. We say thatGisCCAif every connected Cayley graph onGis CCA.

Here are some of our main results:

Theorem 1.3.

1. There is a non-CCA group of ordernif and only ifn≥8andnis divisible by either
4,21, or a number of the formp^{q}·q, wherepandqare prime(see Corollary6.13
and Remark6.14).

2. An abelian group is not CCA if and only if it has a direct factor that is isomorphic to
eitherZ4×Z2or a group of the formZ2^{k}×Z2×Z2, withk≥2(see Proposition4.1).

3. Every dihedral group is CCA(see Corollary5.4).

4. No generalized dicyclic group or semidihedral group is CCA, except thatZ4 is di- cyclic, but is CCA(see Corollary2.8).

5. Every non-CCA group of odd order has a section that is isomorphic to either the nonabelian group of order21or a certain generalization of a wreath product(called a semi-wreathed product) (see Theorem6.8).

6. IfG×H is CCA, thenG andH are both CCA (see Proposition 3.1). The con- verse is not always true (for example, Z4 ×Z2 is not CCA), but it does hold if gcd |G|,|H|

= 1(see Proposition3.2).

We also consider automorphisms ofCay(G;S)that permute the colours, rather than preserving them:

Definitions 1.4.

• An automorphismαof a Cayley graphCay(G;S)iscolour-permutingif it respects
the colour classes; that is, if two edges have the same colour, then their images
underαmust also have the same colour. This means there is a permutationπofS,
such thatα(gs)∈ {α(g)π(s)^{±}^{1}}for allg∈Gands∈S(andπ(s^{−}^{1}) =π(s)^{−}^{1}).

• We say that a groupGisstrongly CCAif every colour-permuting automorphism of every connected Cayley graph onGis affine.

Note that any strongly CCA group is CCA, since colour-preserving automorphisms are colour-permuting (withπ being the identity map on S). The converse is not true. For example, any dihedral group is CCA (as was mentioned above), but it is not strongly CCA if its order is of the form8k+ 4(see Proposition5.6). However, the converse does hold for at least two natural families of groups:

Theorem 1.5. A CCA group is strongly CCA if either:

1. it is abelian(see Proposition4.1), or 2. it has odd order(see Proposition6.4).

Remarks 1.6.

1. It follows from Theorems1.3(2) and1.5(1) that every cyclic group is strongly CCA.

This is also a consequence of the main theorem of [9].

2. Groups that are not strongly CCA seem to be far more likely to be of even order than of odd order. For example, of the28groups of order less than32that are not strongly CCA, only one has odd order (see Section7). In fact, there are only three groups of odd order less than 100 that are not strongly CCA: the non-abelian group G21of order21, the groupG21×Z3 of order63, and the wreath productZ3oZ3, which has order81(see Corollary6.15).

3. If the subgroup consisting of all left-translations is normal in the automorphism group of the Cayley graphCay(G;S), thenCay(G;S)is said to benormal[12]. It is not difficult to see that every normal Cayley graph is strongly CCA (cf. Remark6.2), and that every automorphism of a normal Cayley graph is colour-permuting.

4. The notion of (strongly) CCA generalizes in a natural way to the setting of Cay-
ley digraphs−−→Cay(G;S), by putting the colourson each directed edge of the form
x→ xs. (There is no need to includes^{−}^{1}in the colour.) However, it is very easy
to see that if−−→Cay(G;S)is connected, then every colour-preserving automorphism
of−−→Cay(G;S)is left-translation by some element ofG[11, Thm. 4-8, p. 25], and
that every colour-permuting automorphism is affine [3, Lem. 2.1]. Therefore, both
notions are completely trivial in the directed setting. However, there has been some
interest in determining when every automorphism of−−→Cay(G;S)is colour-permuting
[1,2] (in which case, the Cayley digraph is normal, in the sense of (3)).

### 2 Examples of non-CCA groups

Remark 2.1. Since automorphisms are the only affine functions that fix the identity ele- mente(and left-translations are colour-preserving automorphisms of any Cayley graph), it is easy to see that ifCay(G;S)is CCA, then every colour-preserving automorphism that fixes the identity is an automorphism of the groupG. More precisely:

A Cayley graphCay(G;S)is CCA if and only if, for every colour-preserving auto- morphismϕofCay(G;S), such thatϕ(e) =e, we haveϕ∈AutG.

The same is true with “strongly CCA” in the place of “CCA,” if “colour-preserving” is re- placed with “colour-permuting.” This is reminiscent of the CI (Cayley Isomorphism) prop- erty [7], and this similarity motivated our choice of terminology.

We thank Gabriel Verret for pointing out that the quaternion groupQ8is not CCA. In fact, two different groups of order8are not CCA:

Example 2.2(G. Verret). Z4×Z2andQ8are not CCA.

Proof. (Q8) LetΓ = Cay(Q8;{±i,±j}). This is the complete bipartite graphK4,4. (See Figure1with the labels that are inside the vertices.) Letϕbe the graph automorphism that interchanges the verticeskand−kwhile fixing every other vertex. This is clearly not an automorphism ofGsinceiandjare fixed byϕand generateG, butϕ6= 1. It is, however, a colour-preserving automorphism ofΓ.

(Z4 ×Z2) Let Γ = Cay Z4×Z2;{±(1,0),±(1,1)}

. This is again the complete bipartite graphK4,4. (See Figure1 with the labels that are outside the vertices.) Letϕ be the graph automorphism that interchanges the vertices(0,1)and(2,1)while fixing all of the other vertices. This is clearly not an automorphism ofGsince(1,0)and(1,1)are fixed byϕand generateG, butϕ6= 1. It is, however, a colour-preserving automorphism ofΓ.

1

−1

j

−j

−i i

−k k (0,0)

(2,0)

(1,1)

(3,1)

(3,0)

(1,0) (0,1)

(2,1)

Figure 1: Interchanging the two black vertices while fixing all of the white vertices is a colour-preserving graph automorphism that fixes the identity vertex but is not a group automorphism.

Both of the groups in Example2.2are generalized dicyclic (cf. Definition2.6):

• Q8is the generalized dicyclic group overZ4, and

• Z4×Z2is the generalized dicyclic group overZ2×Z2.

More generally, we will see in Corollary2.8(4) below that no generalized dicyclic group is CCA (unless the cyclic groupZ4is considered to be dicyclic).

We will see in Theorem6.8that the following example is the smallest group of odd order that is not CCA.

Example 2.3. The nonabelian group of order21is not CCA.

Proof. LetG=ha, x|a^{3} =e, a^{−}^{1}xa =x^{2}i. (Sincex=e^{−}^{1}xe =a^{−}^{3}xa^{3}=x^{8}, the
relations implyx^{7}=e, soGhas order21.) By lettingb=ax, we see thatGalso has the
presentation

G=ha, b|a^{3}=e, (ab^{−}^{1})^{2}=b^{−}^{1}ai.

As illustrated in Figure2, every element ofGcan be written uniquely in the form
a^{i}b^{j}a^{k}, where i, j, k∈ {0,±1} and j= 0⇒k= 0.

Define

ϕ(a^{i}b^{j}a^{k}) =

b^{j}a^{−}^{k} ifi= 0,
ab^{−}^{j}a^{k} ifi= 1,
a^{−1}b^{−}^{j}a^{−}^{k} ifi=−1.

Thenϕis a colour-preserving automorphism ofCay G;{a^{±}^{1}, b^{±}^{1}}

(see Figure2). How-
ever,ϕis not affine, since it fixese, but is not an automorphism ofG(becauseϕ(ab) =
ab^{−}^{1}6=ab=ϕ(a)ϕ(b)).

e

b ba

ba^{−}^{1}
b^{−}^{1}

b^{−1}a
b^{−1}a^{−1}

ab a
aba
aba^{−1}

ab^{−1}
ab^{−}^{1}a ab^{−}^{1}a^{−}^{1}

a^{−1}
a^{−1}b

a^{−}^{1}ba a^{−}^{1}ba^{−}^{1}

a^{−}^{1}b^{−}^{1}

a^{−1}b^{−1}a

a^{−}^{1}b^{−}^{1}a^{−}^{1}
1
1
2

2 3

3

4 4

5

5

6 6 7

7 8

8

Figure 2: The colour-preserving automorphismϕfixes every black vertex, but interchanges the two vertices labeled

^{i}

^{, for}

^{1}≤i≤8. Since the neighbours of both copies of

^{i}

^{have}

the same labels (for example, the vertices labeled

^{7}are connected by a black edge to

^{1}

and

^{5}, and by a white edge to

^{6}

^{and}

^{8}), we see thatϕis indeed a colour-preserving automorphism of the graph (if the orientations of the edges are ignored).

See Proposition3.3for a generalization of the following example.

Example 2.4. The wreath productZmoZnis not CCA wheneverm≥3andn≥2.

Proof. This group is a semidirect product

(Zm×Zm× · · · ×Zm)o Zn. For the generatorsa= (1,0,0, . . . ,0),0

andb= (0,0, . . . ,0),1

, the map (x1, x2, x3, . . . , xn), y

7→ (−x1, x2, x3, . . . , xn), y

(negate a single factor of the abelian normal subgroup) is a colour-preserving automor-
phism ofCay ZmoZn;{a^{±}^{1}, b^{±}^{1}}

that fixes the identity element but is not a group auto- morphism.

The following construction provides many additional examples of non-CCA groups by generalizing the idea of Example2.2.

Proposition 2.5. Suppose there is a generating set S of G, an element τ of G, and a subsetT ofS, such that:

• τis an element of order2,

• each element ofSis either centralized or inverted byτ,

• t^{2}=τfor allt∈T,

• the subgrouph(SrT)∪ {τ}iis not all ofG, and

• either

G:h(SrT)∪ {τ}i

>2orτis not in the centre ofG.

ThenGis not CCA.

Proof. For convenience, letH =h(SrT)∪ {τ}i. SincehSi=G, but, by assumption, H 6=G, there exists somex∈TrH. Define

ϕ(g) =

(gτ ifg∈xH, g otherwise.

It is obvious thatϕfixese, sincee /∈xH.

We claim thatϕis is not an automorphism ofG. If|G:H|>2, this follows from the
fact that a nonidentity automorphism cannot fix more than half of the elements ofG. Thus,
we may assume|G:H|= 2. Then, by assumption, there is some elementhofGthat does
not commute withτ. Sinceτcommutes with every element ofT(becauseτ =t^{2}), we see
that we may assumeh∈ H. Ifϕis an automorphism, then, since it is the identity on the
normal subgroupH ofG, butx^{−}^{1}=xx^{−}^{2}=xτ ∈xH, we have:

x^{−}^{1}hx=ϕ(x^{−}^{1}hx) =ϕ(x^{−}^{1})·ϕ(h)·ϕ(x) =x^{−}^{1}τ·h·xτ 6=x^{−}^{1}hxτ^{2}=x^{−}^{1}hx.

This is a contradiction.

Since each element of S is either centralized or inverted byτ, we know that right- multiplication byτis a colour-preserving automorphism ofCay(G;S). Restricting toxH,

this tells us thatϕpreserves colours (and existence) of all edges ofCay(G;S)that have both endvertices inxH.

Now consider an edge fromgtoh, whereg∈xHandh6∈xH. There is some element
t∈T such thatgt=h, and there is an edge of the same colour fromϕ(g) =gτ togτ t^{−}^{1}.
Sincet^{2}=τandτ^{2}=e, we havet^{−}^{1}=τ t. Hence, the edge is fromϕ(g)to

gτ t^{−1}=gt^{2}t^{−1}=gt=h=ϕ(h).

Thusϕpreserves the existence and colour of every edge from a vertex inxHto a vertex outside ofxH. Since the only vertices moved by ϕare in xH, this shows that ϕis a colour-preserving automorphism ofCay(G;S).

Here are a few particular examples to which Proposition2.5can be applied.

Definition 2.6. LetAbe an abelian group of even order. Choose an involutionyofA. The correspondinggeneralized dicyclic groupis

Dic(y, A) =hx, A|x^{2}=y, x^{−}^{1}ax=a^{−}^{1}, ∀a∈Ai.

Definition 2.7. Forn≥1, let

SemiD16n =ha, x|a^{8n} =x^{2}=e, xa=a^{4n}^{−}^{1}xi.

This is asemidihedral(orquasidihedral) group. The term is usually used only whennis a power of2, but the construction is valid more generally.

Corollary 2.8. The following groups are not CCA:

1. Z4×Z2,

2. Z2^{k}×Z2×Z2, for anyk≥2,
3. Q8,

4. every generalized dicyclic group exceptZ4(this generalizes(3)), and 5. every semidihedral group.

Proof. (1) Apply Proposition2.5withτ= (2,0)andS=T ={(1,0),(1,1)}.

(2) Apply Proposition2.5withτ= (2^{k}^{−}^{1},0,0),T ={(2^{k}^{−}^{2},1,0),(2^{k}^{−}^{2},0,1)}, and
S={(1,0,0)} ∪T.

(3) Sincei^{2} =j^{2} =−1, we may apply Proposition2.5withτ =−1andS = T =
{i, j}.

(4) ForG= Dic(y, A) =hx, y, Ai, apply Proposition2.5withτ =yandS =T = xA. (We have

G:h(SrT)∪ {τ}i

=|G:hτi|=|G|/2>2, sinceG6∼=Z4.)

(5) ForG= SemiD16n =ha, xi, apply Proposition2.5withτ=a^{4n},T ={(ax)^{±1}},
andS={x} ∪T. (Note that

G:h(SrT)∪ {τ}i

=|G:hx, τi|=|G|/4≥4.)

### 3 Direct products and semidirect products

Proposition 3.1. IfG1is not strongly CCA, and G2is any group, then G1×G2 is not strongly CCA. Furthermore, the same is true with “CCA” in the place of “strongly CCA.”

Proof. SinceG1is not strongly CCA, some connected Cayley graphCay(G1;S1)onG1

has a colour-permuting automorphismϕ1that is not affine. Letπbe a permutation ofS1,
such thatϕ1(g1s)∈ {ϕ1(g1)π(s)^{±1}}for allg1 ∈G1. (IfG1is not CCA, then we may
assumeπis the identity permutation.) Now, fix any connected Cayley graphCay(G2;S2)
onG2, and let

S= S1× {e}

∪ {e} ×S2 ,

soCay(G1×G2;S)is connected. (It is isomorphic to the Cartesian productCay(G1;S1) Cay(G2;S2).)

Define a permutationϕofG1×G2byϕ(g1, g2) = ϕ(g1), g2

. For all(g1, g2) ∈ G1×G2andsi∈Si, we have

• ϕ (g1, g2)·(s1, e)

= ϕ1(g1s1), g2

∈

ϕ g1, g2

· π(s1), e±1

, and

• ϕ (g1, g2)·(e, s2)

= ϕ1(g1), g2s2

=ϕ(g1, g2)·(e, s2).

Therefore,ϕis a colour-permuting automorphism ofCay(G1×G2;S)(and it is colour- preserving ifπis the identity permutation ofS1).

However, ϕis not affine (since its restriction toG1 is the permutationϕ1, which is not affine). So Gis not strongly CCA (and is not CCA ifπis the identity permutation ofS1).

Proposition3.1tells us that ifG1×G2is CCA, thenG1 andG2must both be CCA.

The converse is not true. (For example,Z4andZ2are both CCA, but Example2.2tells us
that the direct productZ4×Z^{2}is not CCA.) However, the converse is indeed true when the
groups are of relatively prime order:

Proposition 3.2. Assumegcd |G1|,|G2|

= 1. ThenG1×G2is CCA(or strongly CCA) if and only ifG1andG2are both CCA(or strongly CCA, respectively).

Proof. (⇒) Proposition3.1.

(⇐) Let

• G=G1×G2,

• Sbe a generating set ofG,

• ϕbe a colour-permuting automorphism ofCay(G;S)that fixes the identity element (see Remark2.1),

• πi:G1×G2→Gibe the natural projection, and

• kbe a multiple of|G2|that is≡1 (mod|G1|), sog^{k}=π1(g)for allg∈G.

Consider somes∈S, and lett=ϕ(s), soϕ(xs^{i}) =ϕ(x)t^{±}^{i}for allx∈Gandi∈Z.
Then, for allg∈G, we have

ϕ g π1(s)

=ϕ(gs^{k}) =ϕ(g)t^{±}^{k}=ϕ(g)·π1(t)^{±}^{1}. (∗)
Sinceπ1(S)generatesG1, this implies there is a well-defined permutationϕ2ofG2, such
that

ϕ(G1× {g2}) =G1× {ϕ2(g2)}.

By repeating the argument with the roles ofG1andG2 interchanged, we conclude that there is a permutationϕ1ofG1, such that

ϕ(g1, g2) = ϕ1(g1), ϕ2(g2) .

Now, (∗) implies that ϕ1 is a colour-permuting automorphism of Cay G1;π1(S) . Similarly, ϕ2 is a colour-permuting automorphism of Cay G2;π2(S)

. Since each Gi

is CCA, we conclude thatϕi is an automorphism of Gi. Soϕ is an automorphism of G1×G2.

The idea used in Example2.4yields the following result that generalizes the CCA part of Proposition3.1.

Proposition 3.3. SupposeG = H oK is a semidirect product, andCay(H;S0) is a connected Cayley graph ofH, such that:

• S0is invariant under conjugation by every element ofK, and

• there is a colour-preserving automorphismϕ0ofCay(H;S0), such that either

◦ ϕ0is not affine, or

◦ ϕ0(e) = e, and there exist s ∈ S0 and k ∈ K, such thatϕ0(k^{−1}sk) 6=
k^{−1}ϕ0(s)k.

ThenGis not CCA.

Proof. Defineϕ: G→ Gbyϕ(hk) = ϕ0(h)k. We claim thatϕis a colour-preserving automorphism ofCay(G;S0∪K)that is not affine (soGis not CCA, as desired).

Fork1∈K, we have

ϕ(hk k1) =ϕ0(h)kk1=ϕ(hk)k1,

soϕpreserves the colour ofK-edges. Now consider somes∈S0and let^{k}s=ksk^{−}^{1} ∈
S0. Then, sinceϕ0is colour preserving, we have

ϕ(hk s) =ϕ(h^{k}s k) =ϕ0(h^{k}s)k= ϕ0(h) (^{k}s)^{±}^{1}

k=ϕ0(h)ks^{±}^{1}=ϕ(hk)s^{±}^{1},
soϕalso preserves the colour ofS0-edges. Hence,ϕis colour-preserving.

Now, suppose ϕis affine. Then the restriction ϕ0 of ϕto H is also affine, so, by assumption, we must haveϕ(e) =e, soϕis an automorphism ofG. Hence, for alls∈S0

andk∈K, we have

ϕ0(k^{−}^{1}sk) =ϕ(k^{−}^{1}sk) =ϕ(k)^{−}^{1}ϕ(s)ϕ(k) =k^{−}^{1}ϕ(s)k=k^{−}^{1}ϕ0(s)k.

This contradicts the hypotheses of the proposition.

Remark 3.4. Proposition3.3can be generalized slightly: assumeG =HK andH / G (but do not assumeH∩K ={e}, which would makeGa semidirect product). Then the above proof applies if we make the additional assumption thatϕ0(hk) = ϕ0(h)kfor all h∈H andk∈H∩K.

### 4 Abelian groups

The following result shows that all non-CCA abelian groups can be constructed from ex- amples that we have already seen in Corollary2.8(and that CCA and strongly CCA are equivalent for abelian groups).

Proposition 4.1. For an abelian groupG, the following are equivalent:

1. Ghas a direct factor that is isomorphic to eitherZ4×Z2 or a group of the form
Z2^{k}×Z2×Z2, withk≥3.

2. Gis not CCA.

3. Gis not strongly CCA.

Proof. (1⇒2) This is immediate from Corollary2.8and Proposition3.1.

(2⇒3) Obvious.

(3 ⇒ 1) Letϕbe a colour-permuting automorphism of any connected Cayley graph Cay(G;S)onG, such thatϕ(0) = 0. From Proposition3.2(and the fact that any abelian group is the direct sum of its Sylow subgroups), we may assumeGis ap-group for some primep. Then

G∼=Zp^{k}1 ×Zp^{k}2× · · · ×Zp^{km}, withk1≥k2≥ · · · ≥km≥1.

SinceSis a generating set, it is easy to see that there is somes1∈S, such that|s1|=p^{k}^{1}.
Also, it is a basic fact about finite abelian groups that every cyclic subgroup of maximal
order is a direct summand [4, Lem. 1.3.3, p. 10]. Therefore, by induction oni, we see that
there exists1, . . . , sm∈S, such that if we letGi=hs1, . . . , sii, then

Gi∼=Gi−1×Zp^{ki} and G∼=Gi×Zp^{ki+1}× · · · ×Zp^{km}, for eachi.

It is important to note that each element ofGican be written uniquely in the form

g+rsi, withg∈Gi−1and−p^{k}^{i}/2< r≤p^{k}^{i}/2(andr∈Z). (†)
For convenience, also let

ti=ϕ(si) and Hi=ht1, . . . , tii.

We will show, by induction oni, that ifGdoes not have any direct summands of the form specified in the statement of the proposition, thenHiis a direct factor ofG, and the restriction ofϕtoGiis an isomorphism ontoHi. (Note that this impliesG/Gi ∼=G/Hi, by the uniqueness of the decomposition ofGas a direct sum of cyclic groups.) Taking i=myields the desired conclusion thatϕis an automorphism ofG.

The base casei= 0is trivial. For the induction step, writeG=Gi−1×G, so
G∼=G/Gi−1∼=Zp^{ki} ×Zp^{ki+1} × · · · ×Zp^{km},

and let :G→Gbe the natural projection. Thenhsii=Gi∼=Zp^{ki}is a direct summand
ofG. Sinceϕis colour-permuting (andHi−1=ϕ(Gi−1)is a subgroup), it is easy to see
that the order oftiinG/Hi−1is equal top^{k}^{i} (the same as the the order ofsiinG/Gi−1),
and thatϕ(p^{k}^{i}si) =p^{k}^{i}ti. This implies that if we define

α:Gi→Hi by α(g+rsi) =ϕ(g) +rti forg∈Gi−1andr∈Z,

thenαis a well-defined isomorphism. So we need only show that the restriction ofϕtoGi

is equal toα(unlessGhas a direct summand of the desired form).

Supposeϕ|^{G}i 6= α. (This will lead either to a contradiction or to a summand of the
desired form.) Sinceϕis colour-permuting and, by definition,αagrees withϕonGi−1,
this implies there is someg∈Gi−1, such thatϕ(g+si)6=α(g+si). However, sinceϕis
colour-permuting, we know

ϕ(g+si) =ϕ(g)±ϕ(si) =α(g)±ti. Sinceα(g+si) =α(g) +ti, the preceding two sentences imply

ϕ(g+si) =α(g)−ti∈Hi−1−ti.

Furthermore, sinceϕis colour-permuting (andϕ(sj) =tj), we know that it maps edges of
colour{s^{±1}_{1} }, . . . ,{s^{±1}_{i}_{−}_{1}}to edges of colour{t^{±1}_{1} }, . . . ,{t^{±1}_{i}_{−}_{1}}, so

ϕ(x+h)∈ϕ(x) +Hi−1for allx∈Gandh∈Hi−1. Takingx=siandh=gyields

ϕ(g+si)∈Hi−1+ϕ(si) =Hi−1+ti.

This contradicts the uniqueness ofrin the analogue of (†) forHi, unless1 =p^{k}^{i}/2. Hence,
we must havep^{k}^{i}= 2(soZ2is a direct summand ofG), which meansp= 2andki= 1.

We have

ϕ(g) + 2ti=α(g+ 2si) (definition ofα)

=ϕ(g+ 2si) (g+ 2si=g+p^{k}^{i}si ∈Gi−1)

=ϕ(g)−2ti (ϕ(g+si) =α(g)−ti=ϕ(g)−ti), so4ti = 0. Also note that, since

ϕ(g) +ti =α(g+si)6=ϕ(g+si) =ϕ(g)−ti, we must have2ti6= 0. So|ti|= 4.

Sincehs1, . . . , si−1i=Gi−1, there must existg^{0}∈Gi−1, andj < i, such that
ϕ(g^{0}+si) =α(g^{0}) +ti, but ϕ(g^{0}+sj+si) =α(g^{0}+sj)−ti=α(g^{0}) +tj−ti.
Sinceϕis colour-permuting, we also have

ϕ(g^{0}+sj+si) =ϕ(g^{0}+si)±tj=α(g^{0}) +ti±tj.

Hence,tj−ti = ti±tj, sotj∓tj = 2ti. Since2ti 6= 0, we conclude that2tj = 2ti; hence,|tj|= 4.

Since2^{k}^{j} =|Hj :Hj−1|is a divisor of|tj|, and|tj|= 4, there are two possibilities for
kj:

• Ifkj = 2, thenZ4×Z2∼=Z_{2}kj ×Z2^{ki} is a direct summand ofG, as desired.

• Ifkj = 1, then, since|tj| = 4, there must be some` < j, such thatk` ≥2. This
implies thatZ2^{k`} ×Z2×Z2 ∼=Z2^{k`} ×Z_{2}kj ×Z2^{ki} is a direct summand ofG, as
desired.

Corollary 4.2. Forn ∈ Z^{+}, there is a non-CCA abelian group of ordernif and only if
nis divisible by8.

### 5 Generalized dihedral groups

Definition 5.1. Thegeneralized dihedral groupover an abelian groupAis the group
hσ, A|σ^{2}=e, σaσ=a^{−}^{1}∀a∈Ai.

Lemma 5.2. SupposeDis the generalized dihedral group over an abelian groupA, and ϕis a colour-permuting automorphism of a connected Cayley graphCay(D;S), such that ϕ(e) =e. IfAis strongly CCA, andϕ(S∩A) =S∩A, thenϕis an automorphism ofD.

Proof. Label the elements ofSasS={a1, a2, . . . , ak, σ1, σ2, . . . , σt}, whereai∈Afor 1≤i≤k, andσi6∈Afor1≤i≤t(so eachσiis an involution that inverts the elements ofA). By assumption,{a1, a2, . . . , ak}and{σ1, σ2, . . . , σt}are invariant underϕ. Thus, for eachi, we have

• ϕ(ai) =a^{0}_{i}for somea^{0}_{i}∈ {a1, a2, . . . , ak}, and

• ϕ(σi) =σ^{0}_{i}for someσ_{i}^{0} ∈ {σ1, σ2, . . . , σt}.

Notice that since σ1, . . . , σt are involutions, eachσi is its own inverse. Therefore,
whenever σ is a word in σ1, . . . , σt andg ∈ D, the fact thatϕ is a colour-permuting
automorphism means thatϕ(gσ) =ϕ(g)σ^{0}, whereσ^{0} is formed fromσby replacing each
instance ofσiinσbyσ_{i}^{0}. Therefore, if we letΣbe the subgroup generated by{σ1, . . . , σt},
thenϕis a colour-preserving automorphism of the Cayley graphCay(D;S∪Σ). Hence,
there is no harm in assuming thatS=S∪Σ, soΣ⊆S.

SincehS∩Aiis normal inD(in fact, every subgroup ofAis normal, because every
element ofD either centralizes or inverts it), we haveD = hS ∩AiΣ. ThereforeA =
hS∩Ai(Σ∩A) =hS∩Ai, soCay(A;S∩A)is connected. Sinceϕis colour-preserving, and
ϕ(S∩A) =S∩A, this implies thatϕ(A) =A. Soϕis a colour-permuting automorphism
of the connected Cayley graphCay(A;S∩A). Since, by assumption,Ais strongly CCA,
this implies thatϕ|^{A}is an automorphism ofA. Soϕ(ab^{}) =ϕ(a)ϕ(b)^{}for alla, b∈ A
and∈Z.

Now we are ready to show thatϕis an automorphism ofD. Letg, h∈ D. Then we
may writeg =aσandh=beσ, wherea, b∈ Aandσ,eσ∈ {e, σ1}. For convenience, let
∈ {±1}, such thatσcσ=c^{}for allc∈A. Note that, sinceσ^{0}_{1}∈ {σ1, . . . , σt}, we know
thatσ1andσ_{1}^{0} both invertA, so we also haveσ^{0}cσ^{0} =c^{}. Then

ϕ(gh) =ϕ(aσ·beσ) =ϕ(ab^{}·σσ) =e ϕ(a)ϕ(b)^{}·σ^{0}eσ^{0}=ϕ(a)σ^{0}·ϕ(b)eσ^{0}=ϕ(g)·ϕ(h).

Sinceg, h∈Dare arbitrary, this proves thatϕis an automorphism ofD.

Proposition 5.3. The generalized dihedral groupDover an abelian groupAis CCA if and only ifAis CCA.

Proof. (⇐) Note that ifϕis any colour-preserving automorphism of a connected Cayley graphCay(D;S), thenϕ(S∩A) =S∩A, sinceAis closed under inverses. Furthermore, Ais strongly CCA, since it is assumed to be CCA and every CCA abelian group is strongly CCA (see Proposition4.1). Therefore, Lemma5.2implies thatϕis a group automorphism.

SoDis CCA.

(⇒) WriteD =Aohσi. SinceAis not CCA, there is a colour-preserving automor- phismϕ0 of some connected Cayley graphCay(A;S), such thatϕ0 is not affine. Since

σinverts every element ofS, it is easy to see thatCay D;S∪ {σ}

is isomorphic to the Cartesian productCay(A;S)P2. So the proof of Proposition 3.1provides a colour- preserving automorphismϕofCay D;S∪ {σ}

whose restriction toAisϕ0, which is not an affine map. Therefore,ϕis not affine.

The following result is the special case whereAis cyclic (since Proposition4.1implies that every cyclic group is CCA).

Corollary 5.4. Every dihedral group is CCA.

Lemma 5.5. IfT is a generating set of a groupH, andσis a nontrivial automorphism
ofH, such thatσ(t)∈ {t^{±1}}for everyt∈T, then the groupG= (Hohσi)×Z2is not
strongly CCA.

Proof. LetG^{0} = H ×Z2×Z2 and define ϕ: G → G^{0} byϕ(h, σ^{x}, y) = (h, x, y)for
h ∈ H andx, y ∈ Z2. Sinceσ(t) ∈ {t^{±}^{1}} for everyt, it is easy to verify that ϕis a
colour-respecting isomorphism

from Cay G; (H, e,0)∪ {(e, σ,0),(e,0,1)} to Cay G; (H,0,0)∪ {(e,1,0),(e,0,1)} .

Permuting the twoZ2 factors of G^{0} provides an automorphism of G^{0} that preserves the
generating set, and therefore corresponds to a colour-permuting automorphism of the two
Cayley graphs. However, it is not an automorphism ofG, since it takes the central element
(e, e,1)to(e, σ,0), which is not central (since the automorphismσis nontrivial).

Proposition 5.6. The generalized dihedral group over an abelian groupAis strongly CCA if and only if eitherAdoes not haveZ2as a direct factor, orAis an elementary abelian 2-group(in which case, the generalized dihedral group is also an elementary abelian2- group).

Proof. (⇒) SupposeA=A^{0}×Z2, andA^{0}is not elementary abelian. Then the generalized
dihedral groupAohσioverAis isomorphic to(A^{0}ohσi)×Z2, so Lemma5.5tells us
that it is not strongly CCA.

(⇐) LetD=Aohσibe the generalized dihedral group overA, and letϕbe a colour- permuting automorphism of a connected Cayley graphCay(D;S), such thatϕ(e) =e. We may assumeAdoes not haveZ2as a direct factor (otherwise, the desired conclusion follows from the fact that every elementary abelian2-group is strongly CCA (see Proposition4.1)).

From Proposition4.1, we see thatAis strongly CCA. Hence, the desired conclusion will follow from Lemma5.2if we show thatϕ(S∩A) =S∩A.

Leta∈S∩A. Sinceϕis colour-permuting, we have|ϕ(s)|=|s|for alls∈S. Also, we know that|g| = 2for allg ∈ DrA. Therefore, it is obvious thatϕ(a) ∈ S∩Aif

|a| 6= 2.

So we may assume|a|= 2. SinceAdoes not haveZ2as a direct factor, this implies
thatais a square inA: that is, we havea=x^{2}, for somex∈A. Also, sinceCay(D;S)is
connected, we may writex=s1s2· · ·snfor somes1, . . . , sn ∈S. Soa= (s1s2· · ·sn)^{2}
can be written as a word in which every element ofS occurs an even number of times.

Sinceϕis colour-permuting, this implies thatϕ(a)can be written as a word in which, for
eachs∈S, the total number of occurrences of eithersors^{−1}is even. Sincesands^{−1}both
either centralizeAor invert it, this implies thatϕ(a)centralizesA. Since every element of
DrAinvertsA, we conclude thatϕ(a)∈A, as desired.

### 6 Groups of odd order

The following notation will be assumed throughout this section.

Notation 6.1. For a fixed Cayley graphCay(G;S):

• A^{0}is the group of all colour-preserving automorphisms ofCay(G;S).

• Gb is the subgroup of A^{0} consisting of all left translations by elements ofG. (Al-
though we do not need this terminology, it is often called theleft regular representa-
tionofG.)

• He is the stabilizer of the identity element ein Cay(G;S), for any subgroupH
ofA^{0}.

Remark 6.2. It is well known (and very easy to prove) that a permutation ofGis affine if and only if it normalizesGb(see, for example [10, Lem. 2]).

Lemma 6.3. A^{0}eis a2-group.

Proof. Letϕ∈A^{0}e, soϕis a colour-preserving automorphism ofCay(G;S)that fixese.

IfCis any monochromatic cycle throughe, then eitherϕis the identity onCorϕreverses
the orientation ofC. Therefore,ϕ^{2}acts trivially on the union of all monochromatic cycles
that containe. This implies thatϕ^{2}acts trivially on all vertices at distance≤1frome.

Repeating the argument shows thatϕ^{2}^{k}acts trivially on all vertices at distance≤k−1
frome. Forklarger than the diameter ofCay(G;S), this implies thatϕ^{2}^{k}is trivial. So the
order ofϕis a power of2.

Proposition 6.4. Let Cay(G;S)be a connected Cayley graph on a groupGof odd or- der. If every colour-preserving automorphism of Cay(G;S)is affine, then every colour- permuting automorphism is affine.

Proof. LetA^{•} be the group of all colour-permuting automorphisms ofCay(G;S). Since
A^{•} acts on the set of colours, and A^{0} is the kernel of this action (and the kernel of a
homomorphism is always normal), it is obvious thatA^{0}/ A^{•}. Also, since Gis CCA,
we haveG /b A^{0} (cf. Remark 6.2). Furthermore, |G| is odd,|A^{0}e|is a power of 2, and
A^{0}=Gb·A^{0}e. Therefore,Gbis the (unique) largest normal subgroup of odd order inA^{0}. The
uniqueness implies thatGbischaracteristicinA^{0}. (That is, it is fixed by all automorphisms
ofA^{0}.) SoGbis a characteristic subgroup of the normal subgroupA^{0}ofA^{•}. Although a
normal subgroup of a normal subgroup need not be normal, it is well known (and easy to
prove) that any characteristic subgroup of a normal subgroup is normal [4, Thm. 2.1.2(ii),
p. 16]. ThereforeG /b A^{•}. This implies thatGis strongly CCA (see Remark6.2).

Wreath productsZmoZ^{n}provide examples of non-CCA groups of odd order (see Exam-
ple2.4). We will see in Theorem6.8that the following slightly more general construction
is essential for understanding many of the other non-CCA groups of odd order.

Example 6.5. Letαbe an automorphism of a groupA, and letn ∈ Z^{+}. Then we can
define an automorphismαeofA^{n}by

α(we 1, . . . , wn) = α(wn), w1, w2, . . . , wn−1 .

It is easy to see that the order ofαeisntimes the order ofα, so we may form the corre-
sponding semidirect productA^{n}o Zn|α|. Let us call this thesemi-wreathed product of
AbyZn, with respect to the automorphismα, and denote itAo^{α}Zn. (Ifαis the trivial
automorphism, then this is the usual wreath productAoZn.)

Negating the first coordinate, as in Example2.4, shows that ifn >1andAis abelian,
but not an elementary abelian2-group, thenAo^{α}Znis not CCA.

Remark 6.6. Because it may be of interest to find minimal examples, we point out that
any semi-wreathed product of odd order satisfying the conditions in the final paragraph
of Example6.5must contain a subgroup that is isomorphic to a semi-wreathed product
Ao^{α}Zq, where Ais an elementary abelianp-group,pandqare primes (not necessarily
distinct),αis an automorphism ofq-power order, and no nontrivial, proper subgroup ofA
is invariant underα.

Definition 6.7([4, p. 5]). LetGbe a group. For any subgroupsH andKofG, such that K / H, the quotientH/Kis said to be asectionofG.

Theorem 6.8. Any non-CCA group of odd order has a section that is isomorphic to either:

1. a semi-wreathed productAo^{α}Zn (see Example6.5), whereAis a nontrivial, ele-
mentary abelian group(of odd order)andn >1, or

2. the(unique)nonabelian group of order21.

Proof. AssumeCay(G;S)is a connected Cayley graph on a group Gof odd order that
does not have a section as described in either (1) or (2). We will show, by induction on the
order, that ifAis any subgroup ofA^{0}that containsG, thenb Gbis a normal subgroup ofA.
(Then takingA=A^{0}implies thatGis CCA (see Remark6.2).)

It is important to note that this conclusion impliesGbis acharacteristicsubgroup ofA (because Lemma6.3implies thatGb is the unique largest normal subgroup of odd order).

For convenience, we writeGbJAwhenGbis characteristic.

LetNbe a minimal normal subgroup ofA. Then Nis either elementary abelian or the direct product of (isomorphic) nonabelian simple groups [4, Thm. 2.1.5, p. 17], and we consider the two possibilities as separate cases.

Case 1.AssumeNis elementary abelian. Since the Sylow2-subgroupAe, being the sta- bilizer of a vertex, does not contain any normal subgroups ofA, we know thatNis not contained in a Sylow2-subgroup. Hence, Nis not a 2-group, so it must be a p-group for some odd primep. Therefore, sinceGb is a maximal subgroup of odd order, we have N⊆G, sob

N=N, for some (elementary abelian) normal subgroupb NofG.

LetN^{+} be the largest normal subgroup ofAthat is contained inNAe. SinceNAeis
the stabilizer of a point under the action ofAon the spaceG/N ofN-orbits, we know that
N^{+} is the kernel of the action ofAonG/N, soA/N^{+} is a group of colour-preserving
automorphisms of Cay(G/N;S), where S is the image ofS in G/N.. Therefore, by
induction on|A|, we know thatGNb ^{+}/N^{+} is normal inA/N^{+}, soGNb ^{+}is normal inA.
Then we may assumeGbN^{+} = A, for otherwise, by induction on|A|, we would know
GbJGNb ^{+}, soG /b A, as desired. Since|G|is odd, this implies thatN^{+}contains a Sylow
2-subgroup ofA. In fact, sinceN^{+}is normal and all Sylow2-subgroups are conjugate, this

implies thatN^{+}contains every Sylow2-subgroup. In particular, it containsAe. Therefore
N^{+}=NAe, so

NAe/A.

This means thatAeacts trivially onG/N, so, for every s ∈ S rN,Aepreserves the
orientation of everys-edge. (This uses the fact that, since|s|is odd,s6≡s^{−}^{1} (mod N)if
s /∈N.) This implies:

forϕ∈Ae,g∈G, andx∈ hSrNi, we haveϕ(gx) =ϕ(g)x. (6.9)
Let (S ∩N)^{h}^{S}^{r}^{N}^{i} = {gsg^{−}^{1} | s ∈ S ∩N, g ∈ hS rNi }. Now, suppose t ∈
(S∩N)^{h}^{S}^{r}^{N}^{i}andh∈N. There existss∈S∩Nandx∈ hSrNi, such thatxsx^{−}^{1}=t.

From (6.9) and the fact thatϕis colour-preserving, we see that

ϕ(h t) =ϕ(h xsx^{−}^{1}) =ϕ(h)x s^{±}^{1}x^{−}^{1}=ϕ(h)t^{±}^{1}.
Hence,ϕ|^{N} is a colour-preserving automorphism of

Cay

N; (S∩N)^{h}^{S}^{r}^{N}^{i}∪ hSrNi ∩N
.
SinceSgeneratesG, it is easy to see that this Cayley graph is connected.

Note thatC_{A}e(N)is normalized by bothNandAe, so it is a normal subgroup ofNAe.
Therefore, it must be trivial (since the largest normal2-subgroup ofNAeis characteristic,
and is therefore normal inA, but the stabilizerAedoes not contain any nontrivial normal
subgroups ofA). So

Aeacts faithfully by conjugation onN. (6.10)
Also, we know thatϕ|^{N} is an automorphism ofN (by Remark6.2, sinceϕnormal-
izes N = N). Since, being a colour-preserving automorphism,b ϕeither centralizes or
inverts every element of the generating set ofN, this implies thatϕ^{2}|^{N} is trivial. Since
this is true for everyϕ∈ Ae, we conclude thatAeacts onN via an elementary abelian
2-group. From (6.10), we conclude thatAeis elementary abelian.

We can think ofNas a vector space overZp, and, for each homomorphismγ: A→ {±1}, let

Nγ ={n∈N|ana^{−}^{1}=γ(a)nfor alla∈Ae}.

(This is called the “weight space” associated to γ.) Since every linear transformation
satisfying T^{2} = I is diagonalizable, and Ae is commutative, the elements of Ae can
be simultaneously diagonalized. This means that if we let Γ =

γ | Nγ 6= {0} , then, since eigenspaces for different eigenvalues are always linearly independent, we have N = L

γ∈ΓNγ. This direct-sum decomposition is canonically defined from the action
ofAeonN. SinceGbacts onNAe(by conjugation), we conclude that the action ofGbonN
by conjugation must permute the weight spaces. More precisely, there is an action ofG
onΓ, such thatbgNγbg^{−1}=Ngγ for allg∈G. SinceN is abelian, this factors through to a
well-defined action ofG/N onΓ.

If theG-action onΓis trivial, then every weight space isG-invariant, which implies that the action ofGbonNcommutes with the action ofAe. SinceAeacts faithfully, we conclude thatGbcentralizesAeN/N; that is,[G,b Ae]⊆N⊆G. Sob AenormalizesG, asb desired.

We may now assume that theG-action is nontrivial, so there is someg ∈ Gwith an
orbit of some lengthn >1onΓ. Letγ0be an element of this orbit, sobg^{n}normalizesNγ0.
SinceSrNgeneratesG/N, we may assumeg∈SrN, so (6.9) tells us thathbgi ∩Nis
centralized byAe. However, the minimality ofNimplies thatC_{N}(Ae) =N∩Z(NAe)is
trivial. Therefore,hN,bgi=Nohbgiis a semidirect product. So

hNγ0,gbi=

M

γ∈hgiγ_{0}Nγ

ohbgi.

Then modding outC_{hb}gi(Nγ_{0})yields a section ofGbthat is isomorphic toNγ_{0}o^{α}Zn, where
αis the automorphism ofNγ0induced by the conjugation action ofbg^{n}. SoGhas a semi-
wreathed section, as described in (1). This completes the proof of this case.

Case 2.AssumeN = L1× · · · ×Lr, where eachLi is a nonabelian simple group, and Li ∼= L1 for alli. We know thatA = GAe e,Aeis a2-group, and|G| is odd, soGb is a2-complement inA. (By definition, this means that|Gb|is odd and|A : Gb|is a power of2 [6, p. 88].) SoL1 is a nonabelian simple group that has a2-complement (namely, Gb∩L1). By using the Classification of Finite Simple Groups, it can be shown that this impliesL1∼= PSL(2, p), for some Mersenne primep≥7(see [8, Thm. 1.3]).

Note thatAe∩Li is a Sylow 2-subgroup ofPSL(2, p). Therefore, it is dihedral [4, Lem. 15.1.1(iii)] and has orderp+ 1(becausepis a Mersenne prime). Let

• Cibe the unique cyclic subgroup of order(p+ 1)/2inAe∩Li,

• C^{2}i be the unique subgroup of index2inCi, and

• C^{2}=C^{2}1× · · ·C^{2}r⊂Ae∩(L1× · · · ×Lr).

Since every element ofCi is a colour-preserving automorphism, it either fixes or inverts
each element ofS, so we know thatC^{2}i fixes every element ofS. Since stabilizers are
conjugate, this impliesbs^{−}^{1}C^{2}bs⊆Ae, for everys∈S. We must havep >7, for otherwise
Gb∩Li, being the2-complement ofPSL(2,7), would be the nonabelian group of order21,
as in (2). This implies thatC^{2}i is the unique cyclic subgroup of order (p+ 1)/4 in the
dihedral groupAe∩Li, so we must havebs^{−}^{1}C^{2}bs=C^{2}, which means thatbsnormalizesC^{2}.
Since this holds for everysin the generating setS, we conclude thatGbnormalizesC^{2}.

Note thatAenormalizesAe∩N, and thatC^{2}JAe∩N(since, as was mentioned above,
Ciis the unique cyclic subgroup of its order inAe∩Li). Therefore,C^{2}/Ae. We conclude
thatC^{2}is normal inGAb e =A. SoC^{2}1=C^{2}∩L1is normal inL1, contradicting the fact
thatL1is simple.

Lemma 6.11. To prove a groupGis strongly CCA(or CCA), it suffices to consider only the connected Cayley graphsCay(G;S), such that every element ofS has prime-power order.

Proof. Supposeϕis a colour-permuting automorphism of some connected Cayley graph
Cay(G;S). There is a permutationπofS, such thatϕ(gs) =ϕ(g)π(s)^{±}^{1}, for allg∈G
ands∈S. (Furthermore, ifϕis colour-preserving, thenπcan be taken to be the identity
permutation.) By induction onk, this implies ϕ(gs^{k}) = ϕ(g)π(s)^{±}^{k}, for all k ∈ Z.
Hence, if we letS^{∗} ={s^{k} |s∈S, k∈Z}, thenϕis a colour-permuting automorphism
ofCay(G;S^{∗}). Now, let

S0={t∈S^{∗}| |t|is a prime-power}.

Thenϕis a colour-permuting automorphism ofCay(G;S0), andS0 generates G, since every elementsof the generating setScan be written as a product of elements ofhsithat have prime-power order [4, Thm. 1.3.1(iii), p. 9], and therefore belong toS0. (Furthermore, ϕis colour-preserving if the permutationπis the identity permutation.)

Lemma 6.12. Suppose

• Cis a cyclic, normal subgroup of a groupH,

• |C|is relatively prime to|H:C|,

• no element ofHrCcentralizesC, and

• αis any automorphism ofH. Thenα(h)∈hC, for everyh∈H.

Proof. Since no other subgroup ofH has the same order asC, we know thatα|^{C} is an
automorphism ofC, so there existsr∈Z, such thatα(c) =c^{r}, for everyc∈C. Then, for
anyh∈Handc∈C, we have

α(h)c^{r}α(h)^{−1}=α(h)α(c)α(h)^{−1}=α(hch^{−1}) = (hch^{−1})^{r}=hc^{r}h^{−1},
soh^{−}^{1}α(h)centralizesC. By assumption, this impliesh^{−}^{1}α(h)∈C, as desired.

Corollary 6.13. The following are equivalent:

1. There is a group of ordernthat is not CCA.

2. There is a group of ordernthat is not strongly CCA.

3. n ≥ 8, andnis divisible by either4,21, or a number of the formp^{q} ·q, wherep
andqare primes(not necessarily distinct)andpis odd.

Proof. We prove (1⇔3) and (1⇔2).

(3 ⇒ 1) Ifnis divisible by4, then there is a generalized dicyclic group of ordern,
which is not CCA (see Corollary2.8(4)). The nonabelian group of order 21 and the wreath
productZpoZq (which is of orderp^{q}·q) are not CCA (see Examples2.3and2.4). Taking
an appropriate direct product yields a non-CCA group whose order is any multiple of these
(see Proposition3.1).

(1⇒3) Assume there is a groupGof ordernthat is not CCA, butnis not divisible by
4,21, or a number of the formp^{q}·q. From Theorem6.8, we see thatnis even. (Otherwise,
n=|G|is divisible by the order of a semi-wreathed product|Ao^{α}Zk|. If we letpandqbe
prime divisors of|A|andk, respectively, then|Ao^{α}Zk|=|A|^{k}·kis a multiple ofp^{q}·q.)
Furthermore,nmust be square-free, for otherwise it is a multiple of either4orp^{2}·2, for
some primep. Therefore,Gis a semidirect productZko Z`.

We may assume the centre ofGis trivial, for otherwise we can writeGas a nontrivial direct product, so Proposition3.2(and induction onn) implies thatGis CCA. Therefore, kis odd (so`is even), so we may writeG=Zko(Zm×Z2), andZm×Z2acts faithfully onZk. LetH =Zko Zm, so|H|=kmis odd, andHis the (unique) subgroup of index2 inG.

Letϕbe a colour-preserving automorphism of a connected Cayley graphCay(G;S).

(We wish to show thatϕis affine.) There is no harm in assuming that every element ofS has prime order (see Lemma6.11). Fix somet∈Swith|t|= 2.

We claim we may assume thatt is the only element of order2 inS, and thatH = hSr{t}i. To see this, let

• Tbe the set of all elements of order2inS, and

• S^{0}={t} ∪ {uv|u, v∈T, u6=v} ∪(SrT).

It is easy to see thatϕis a colour-preserving automorphism of the connected Cayley graph
Cay(G;S^{0}), and thatG=hSr{t}ihti. This establishes the claims.

From Theorem 6.8(and the fact that |H| is odd), we know that ϕ|^{H} is affine. By
composing with a left translation, we may assume thatϕfixese. Thenϕ|^{H} is a group
automorphism. By composing with an automorphism ofZk o(Zm×Z2)of the form
(x, y, z)7→(x^{r}, y, z), we may assumeϕ|Zkis the identity map. Also, sinceϕ(s)∈ {s^{±1}}
for everys ∈ S, and|H/Zk| = mis odd, Lemma6.12implies that ϕalso fixes every
element of(S∩H)r Zk. Hence,ϕ|^{H}is an automorphism that fixes every element of a
generating set, soϕ(h) =hfor everyh∈H. Sinceϕ(ht) =ϕ(h)t=ht, for allh∈H
(becauseϕis colour-preserving andt=t^{−}^{1}), we conclude thatϕfixes every element ofG,
and is therefore affine, as desired.

(1⇒2) Obvious.

(2 ⇒1) Assume there is a groupGof ordernthat is not strongly CCA, butnis not
divisible by4,21, or a number of the formp^{q}·q. Letϕbe a colour-permuting automorphism
of some connected Cayley graphCay(G;S), such thatϕ(e) =e.

As in the proof of (1⇒3) above, we see that we may assume|G|is square-free, and we may writeG=Zko(Zm×Z2), whereZm×Z2acts faithfully onZk. LetH =Zko Zm

be the (unique) subgroup of index2inG. From (1 ⇒3) above, we know thatGis CCA,
soG /b A^{0}. Hence,Hb JA0(since it is the unique largest normal subgroup of odd order),
soϕnormalizesHb. This implies that the restriction ofϕtoHis an automorphism ofH.

For each s ∈ S, letes = ϕ(s) ∈ S. To prove that ϕ is affine, it suffices to show
ϕ(xs) = ϕ(x)esfor allx ∈ Gands ∈ S (see Remark1.6(4)). If this is not the case,
then, sinceϕis colour-permuting, there must be somex, such thatϕ(xs) =ϕ(x)se^{−1}(and
es^{−}^{1}6=es, which means|s| 6= 2). This will lead to a contradiction.

We may assume every element ofShas prime order (see Lemma6.11). Since|s| 6= 2,
this impliess∈H. Then, sinceϕ|^{H} is an automorphism, but

ϕ(xs) =ϕ(x)es^{−}^{1}=ϕ(x)ϕ(s)^{−}^{1}6=ϕ(x)ϕ(s),

we must havex /∈H. SinceH has only two cosets, and there must be some element ofS that is not inH, this implies that we may assumex∈ S, after multiplying on the left by an appropriate element ofH (and using the fact thatϕnormalizesHb). Note that, since x /∈H, and every element ofShas prime order, this implies|x|= 2. So the order ofxeis also2, which impliesx /e∈H(since|H|is odd).

Sinceϕis colour-permuting, we have

ϕ(xs) =ϕ(^{x}s x) =ϕ(^{x}s)ex.

Also, by the choice ofxands, we have

ϕ(xs) =ϕ(x)es^{−}^{1}=exes^{−}^{1}.
Therefore

ϕ(^{x}s) =^{e}^{x}se^{−}^{1}.

SinceZmacts faithfully onZk, we haveα(h)≡h (mod Zk), for every automorphismα
of H (see Lemma 6.12). Since ϕand conjugation by xare automorphisms of H, this
impliess≡s^{−}^{1} (modZ^{k}). Since|s|is odd, we conclude thats∈Z^{k}.

Then, since the automorphism group of a cyclic group is abelian, we have
ϕ(^{x}s) =^{x}ϕ(s) =^{x}es,

sox^{−}^{1}xemust invertes. But this is impossible, because, as was mentioned above,xandex,
being of order2, cannot be inH, so they are both in the other coset ofH, sox^{−}^{1}xe∈H
has odd order. This contradiction completes the proof thatϕis affine.

Remark 6.14. It is not necessary to assumepis odd in the statement of Corollary6.13(3),
because2^{q}·qis divisible by4, which is already in the list of divisors.

Theorem6.8implies that very few small groups of odd order fail to be strongly CCA:

Corollary 6.15. LetG21 =Z7o Z3be the(unique)nonabelian group of order21. Then the only groups of odd order less than100that are not strongly CCA areG21,G21×Z3, andZ3oZ3.

Proof. SupposeGis a group of odd order, such thatGis not strongly CCA and|G|<100.

From Corollary 6.13, we see that |G| is divisible by either 21 or 3^{3}· 3 = 81. Since

|G|<100, this implies that|G|is either21,21×3 = 63, or3^{3}·3 = 81. Also,Gmust be
nonabelian (see Corollary4.2).

• The nonabelian groupG21of order21is not CCA (see Example2.3).

• There are two nonabelian groups of order63. One of them, the direct productG21× Z3, is not CCA (see Proposition3.1).

• Theorem6.8implies thatZ3oZ3is the only non-CCA group of order81(see also Example2.4).

To complete the proof, we sketch a verification that the following group of order63is CCA:

G=Z7o Z9=hx, a|x^{7}=a^{9}=e, a^{−1}xa=x^{2}i.

Letϕbe a colour-preserving automorphism of a connected Cayley graphCay(G;S), such
thatϕ(e) =e. We may assumeSis either{a^{±}^{1}, x^{±}^{1}}or{a^{±}^{1},(ax)^{±}^{1}}, after discarding
redundant generators, applying an automorphism ofG, and replacing some elements by
appropriate powers (cf. the proof of Lemma6.11).

If S = {a^{±}^{1}, x^{±}^{1}}, then we may assume ϕ(x) = x, by composing with an au-
tomorphism of G. Also, since ϕ is colour-preserving, it must pass to a well-defined
automorphism of the cycle Cay G/hxi;{a^{±}^{1}}

, so there exists ∈ {±1}, such that
ϕ(ga) = ϕ(g)a^{}for allg ∈ G. Then, since(1,1)is the only pair(, δ) ∈ {±1}^{2} that
satisfiesa^{−}^{}x^{δ}a^{} = x^{2}, we see thatϕ(x^{i}a^{j}) = x^{i}a^{j} for alliandj, soϕis the identity
map, which is certainly affine.

Assume, now, thatS = {a^{±1},(ax)^{±1}}. Leta1 = aanda2 = xa. For anyg ∈ G
and ∈ {±1}, ifϕ(g a1) = ϕ(g)a^{}_{1}, then, sincea^{3}_{1} = a^{3}_{2} (andϕis colour-preserving),
we haveϕ(g s^{m}) =ϕ(g)s^{m}, for allmand alls∈S. SinceSgeneratesG, this implies
ϕ(gs) =ϕ(g)s^{}for allgand alls∈S. Soϕis affine.