ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 11 (2016) 189-213 On colour-preserving automorphisms of Cayley graphs Ademir Hujdurovic *, Klavdija Kutnar t University ofPrimorska, FAMNIT, Glagoljaska 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 We study the automorphisms of a Cayley graph that preserve its natural edge-colouring. More precisely, we are interested in groups G, such that every such automorphism of every connected Cayley graph on G has 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. Let S be a subset of a group G, such that S = S-1. (All groups and all graphs in this paper are finite.) • The Cayley graph of G, with respect to S, is the graph Cay(G; S) whose vertices are the elements of G, and with an edge x — xs, for each x G G and s G 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 Hujdurovic), klavdija.kutnar@upr.si (Klavdija Kutnar), dave.morris@uleth.ca (Dave Witte Morris), joy.morris@uleth.ca (Joy Morris) charchar This work is licensed under http://creativecommons.Org/licenses/by/3.0/ Abstract 190 Ars Math. Contemp. 11 (2016) 147-156 • Cay(G; S) has a natural edge-colouring. Namely, each edge of the form x — xs is coloured with the set {s, s-1}. (In order to make the colouring well-defined, it is necessary to include s-1, because x — xs is the same as the edge xs — x, which is of the form y — ys-1, with y = xs.) Note that Cay(G; S) is connected if and only if S generates G. Also note that a permutation ^ of G is a colour-preserving automorphism of Cay(G; S) if and only if we have y(xs) G {^(x) s±:L}, for each x G G and s G S. For any g G G, the left translation x ^ gx is a colour-preserving automorphism of Cay(G; S). In addition, if a is an automorphism of the group G, such that a(s) G {s±:} for all s G S, then a is also a colour-preserving automorphism of Cay(G; S). We will see that, in many cases, every colour-preserving automorphism of Cay(G; S) is obtained by composing examples of these two obvious types. Definition 1.2. Let G be a group. 1. A function ^: G ^ 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 y(x) = a(gx), for some a G Aut G and g G G. 2. A Cayley graph 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.) 3. We say that G is CCA if every connected Cayley graph on G is CCA. Here are some of our main results: Theorem 1.3. 1. There is a non-CCA group of order n if and only if n > 8 and n is divisible by either 4, 21, or a number of the form pq ■ q, where p and q are prime (see Corollary 6.13 and Remark 6.14). 2. An abelian group is not CCA if and only if it has a direct factor that is isomorphic to either Z4 x Z2 or a group of the form Z2k x Z2 x Z2, with k > 2 (see Proposition 4.1). 3. Every dihedral group is CCA (see Corollary 5.4). 4. No generalized dicyclic group or semidihedral group is CCA, except that Z4 is di-cyclic, but is CCA (see Corollary 2.8). 5. Every non-CCA group of odd order has a section that is isomorphic to either the nonabelian group of order 21 or a certain generalization of a wreath product (called a semi-wreathed product) (see Theorem 6.8). 6. If G x H is CCA, then G and H are both CCA (see Proposition 3.1). The converse is not always true (for example, Z4 x Z2 is not CCA), but it does hold if gcd(|G|, |H|) = 1 (see Proposition 3.2). We also consider automorphisms of Cay(G; S) that permute the colours, rather than preserving them: A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 191 Definitions 1.4. • An automorphism a of a Cayley graph Cay(G; S) is colour-permuting if it respects the colour classes; that is, if two edges have the same colour, then their images under a must also have the same colour. This means there is a permutation n of S, such that a(gs) G {a(g) n(s)±1} for all g G G and s G S (and n(s-1) = n(s)-1). • We say that a group G is strongly CCA if every colour-permuting automorphism of every connected Cayley graph on G is affine. Note that any strongly CCA group is CCA, since colour-preserving automorphisms are colour-permuting (with n 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 form 8k + 4 (see Proposition 5.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 Proposition 4.1), or 2. it has odd order (see Proposition 6.4). Remarks 1.6. 1. It follows from Theorems 1.3(2) and 1.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 the 28 groups of order less than 32 that are not strongly CCA, only one has odd order (see Section 7). In fact, there are only three groups of odd order less than 100 that are not strongly CCA: the non-abelian group G21 of order 21, the group G21 x Z3 of order 63, and the wreath product Z3 I Z3, which has order 81 (see Corollary 6.15). 3. If the subgroup consisting of all left-translations is normal in the automorphism group of the Cayley graph Cay(G; S), then Cay(G; S) is said to be normal [12]. It is not difficult to see that every normal Cayley graph is strongly CCA (cf. Remark 6.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 Cayley digraphs Cay(G; S), by putting the colour s on each directed edge of the form x ^ xs. (There is no need to include s-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 of G [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 element e (and left-translations are colour-preserving automorphisms of any Cayley graph), it is easy to see that if Cay(G; S) is CCA, then every colour-preserving automorphism that fixes the identity is an automorphism of the group G. More precisely: 192 Ars Math. Contemp. 11 (2016) 147-156 A Cayley graph Cay(G; S) is CCA if and only if, for every colour-preserving automorphism p of Cay(G; S), such that p(e) = e, we have p G Aut G. The same is true with "strongly CCA" in the place of "CCA',' if "colour-preserving" is replaced with "colour-permuting'.' This is reminiscent of the CI (Cayley Isomorphism) property [7], and this similarity motivated our choice of terminology. We thank Gabriel Verret for pointing out that the quaternion group Qg is not CCA. In fact, two different groups of order 8 are not CCA: Example 2.2 (G. Verret). Z4 x Z2 and Qg are not CCA. Proof. (Qg) Let r = Cay(Q8; {±i, ±j}). This is the complete bipartite graph K4,4. (See Figure 1 with the labels that are inside the vertices.) Let p be the graph automorphism that interchanges the vertices k and —k while fixing every other vertex. This is clearly not an automorphism of G since i and j are fixed by p and generate G, but p = 1. It is, however, a colour-preserving automorphism of r. (Z4 x Z2) Let r = Cay(Z4 x Z2; {±(1,0), ±(1,1)}). This is again the complete bipartite graph K4 4. (See Figure 1 with the labels that are outside the vertices.) Let p 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 of G since (1,0) and (1,1) are fixed by p and generate G, but p = 1. It is, however, a colour-preserving automorphism of r. □ (0,0) (1,0)( i (1,1) (0,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 Example 2.2 are generalized dicyclic (cf. Definition 2.6): • Qg is the generalized dicyclic group over Z4, and • Z4 x Z2 is the generalized dicyclic group over Z2 x Z2. More generally, we will see in Corollary 2.8(4) below that no generalized dicyclic group is CCA (unless the cyclic group Z4 is considered to be dicyclic). A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 193 We will see in Theorem 6.8 that the following example is the smallest group of odd order that is not CCA. Example 2.3. The nonabelian group of order 21 is not CCA. Proof. Let G = (a, x | a3 = e, a-1xa = x2 }. (Since x = e-1xe = a-3xa3 = x8, the relations imply x7 = e, so G has order 21.) By letting b = ax, we see that G also has the presentation G = ( a, b | a3 = e, (ab-1 )2 = b-1a}. As illustrated in Figure 2, every element of G can be written uniquely in the form aVak, where i, j, k G {0, ±1} and j = 0 ^ k = 0. Define {bj a-k if i = 0, ab-j ak if i = 1, a-1b-j a-k if i = -1. Then ^ is a colour-preserving automorphism of Cay(G; {a±1, b±1^ (see Figure 2). However, ^ is not affine, since it fixes e, but is not an automorphism of G (because y(ab) = ab-1 = ab = y>(a) y>(b)). □ Figure 2: The colour-preserving automorphism ^ fixes every black vertex, but interchanges the two vertices labeled ©, for 1 < i < 8. Since the neighbours of both copies of © have the same labels (for example, the vertices labeled © are connected by a black edge to © and ©, and by a white edge to © and ©), we see that ^ is indeed a colour-preserving automorphism of the graph (if the orientations of the edges are ignored). 194 Ars Math. Contemp. 11 (2016) 147-156 See Proposition 3.3 for a generalization of the following example. Example 2.4. The wreath product Zm I Zn is not CCA whenever m > 3 and n > 2. Proof. This group is a semidirect product (Z m X Zm X • • • X Zm) X Zn. For the generators a = ((1,0,0,..., 0), 0) and b = ((0,0,..., 0), 1), the map ((xi,x2,x3, ...,x„),y) ^ ((-xi,x2,x3, ...,x„),y) (negate a sing(le factor of the abeli)an normal subgroup) is a colour-preserving automorphism of Cay (Zm I Zn; { a±1, b±1}) that fixes the identity element but is not a group automorphism. □ The following construction provides many additional examples of non-CCA groups by generalizing the idea of Example 2.2. Proposition 2.5. Suppose there is a generating set S of G, an element t of G, and a subset T of S, such that: • t is an element of order 2, • each element of S is either centralized or inverted by t, • t2 = t for all t € T, • the subgroup ((S \ T) U {t}} is not all of G, and • either |G : ((S \ T) U {t}} | > 2 or t is not in the centre of G. Then G is not CCA. Proof. For convenience, let H = ((S \ T) U {t}}. Since (S} = G, but, by assumption, H = G, there exists some x € T \ H. Define <^(g) = I gT if g € xH, 1 g otherwise. It is obvious that ^ fixes e, since e € xH. We claim that ^ is is not an automorphism of G. If |G : H | > 2, this follows from the fact that a nonidentity automorphism cannot fix more than half of the elements of G. Thus, we may assume |G : H| = 2. Then, by assumption, there is some element h of G that does not commute with t. Since t commutes with every element of T (because t = t2), we see that we may assume h € H .If ^ is an automorphism, then, since it is the identity on the normal subgroup H of G, but x-1 = xx-2 = xt € xH, we have: x-1hx = <^>(x-1hx) = <^>(x-1) • ^>(h) • ^>(x) = x-1T • h • xt = x-1hxT2 = x-1hx. This is a contradiction. Since each element of S is either centralized or inverted by t, we know that right-multiplication by t is a colour-preserving automorphism of Cay(G; S). Restricting to xH, A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 195 this tells us that ^ preserves colours (and existence) of all edges of Cay(G; S) that have both endvertices in xH. Now consider an edge from g to h, where g G xH and h G xH. There is some element t G T such that gt = h, and there is an edge of the same colour from y(g) = gr to grt-1. Since t2 = t and r2 = e, we have t-1 = rt. Hence, the edge is from y>(g) to grt-1 = gt2t-1 = gt = h = y(h). Thus ^ preserves the existence and colour of every edge from a vertex in xH to a vertex outside of xH. Since the only vertices moved by ^ are in xH, this shows that ^ is a colour-preserving automorphism of Cay(G; S). □ Here are a few particular examples to which Proposition 2.5 can be applied. Definition 2.6. Let A be an abelian group of even order. Choose an involution y of A. The corresponding generalized dicyclic group is Dic(y, A) = (x, A | x2 = y, x-1ax = a-1, Va G A}. Definition 2.7. For n > 1, let SemiD16n = (a, x | a8n = x2 = e, xa = a4n-1x}. This is a semidihedral (or quasidihedral) group. The term is usually used only when n is a power of 2, but the construction is valid more generally. Corollary 2.8. The following groups are not CCA: 1. Z4 x Z2, 2. Z2k x Z2 x Z2,for any k > 2, 3. Q8, 4. every generalized dicyclic group except Z4 (this generalizes (3)), and 5. every semidihedral group. Proof. (1) Apply Proposition 2.5 with r = (2,0) and S = T = {(1,0), (1,1)}. (2) Apply Proposition 2.5 with r = (2k-1,0,0), T = {(2k-2,1,0), (2k-2,0,1)}, and S = {(1,0,0)}U T. (3) Since ¿2 = j2 = -1, we may apply Proposition 2.5 with r = -1 and S = T = {ij }. (4) For G = Dic(y, A) = (x, y, A}, apply Proposition 2.5 with r = y and S = T = xA. (We have |G : ((S \ T) U {r}}| = |G : (r}| = |G|/2 > 2, since G = Z4.) (5) For G = SemiD16n = (a, x}, apply Proposition 2.5 with r = a4n, T = {(ax)±1}, and S = {x} U T. (Note that |G : ((S \ T) U {r}} | = |G : (x, r}| = |G|/4 > 4.) □ 3 Direct products and semidirect products Proposition 3.1. If G1 is not strongly CCA, and G2 is any group, then G1 x G2 is not strongly CCA. Furthermore, the same is true with "CCA" in the place of "strongly CCA!' 196 Ars Math. Contemp. 11 (2016) 147-156 Proof. Since G1 is not strongly CCA, some connected Cayley graph Cay(Gi; Si) on Gi has a colour-permuting automorphism < that is not affine. Let n be a permutation of S1, such that ^1(g1s) G j^1(g1) n(s)±1} for all g1 G G1. (If G1 is not CCA, then we may assume n is the identity permutation.) Now, fix any connected Cayley graph Cay(G2; S2) on G2, and let S = (S1 xje}) U (je}x S2), so Cay(G1 x G2; S) is connected. (It is isomorphic to the Cartesian product Cay(G1; S1) □ Cay(G2; S2).) Define a permutation < of G1 x G2 by <(01 ,02) = (<£>(01), 02). For all (01,02) G G1 x G2 and sj G Sj, we have • <((01,02) • (s1; e)) = (<1(01s1),02) G {<(01,02) • (n(s1),e)±1},and • <((01,02) • (e, = (<1(01),02s^ = <(01,02) • (e, s2). Therefore, < is a colour-permuting automorphism of Cay(G1 x G2; S) (and it is colour-preserving if n is the identity permutation of S1). However, < is not affine (since its restriction to G1 is the permutation < 1 , which is not affine). So G is not strongly CCA (and is not CCA if n is the identity permutation of S1). □ Proposition 3.1 tells us that if G1 x G2 is CCA, then G1 and G2 must both be CCA. The converse is not true. (For example, Z4 and Z2 are both CCA, but Example 2.2 tells us that the direct product Z4 x Z2 is not CCA.) However, the converse is indeed true when the groups are of relatively prime order: Proposition 3.2. Assume gcd(|G1|, |G2|) = 1. Then G1 x G2 is CCA (or strongly CCA) if and only if G1 and G2 are both CCA (or strongly CCA, respectively). Proof. Proposition 3.1. Let • G = G1 x G2, • S be a generating set of G, • < be a colour-permuting automorphism of Cay(G; S) that fixes the identity element (see Remark 2.1), • n : G1 x G2 ^ Gj be the natural projection, and • k be a multiple of |G21 that is = 1 (mod |G11), so 0k = n1 (0) for all 0 G G. Consider some s G S, and let t = <(s), so <(xsj) = <(x) t±j for all x G G and i G Z. Then, for all 0 G G, we have <(0n1(s)) = <(0sk) = <(0) t±k = <(0) • n1(t)±1. (*) Since n1(S) generates G1, this implies there is a well-defined permutation <2 of G2, such that <(G1 x {02}) = G1 x {<2(02)}. A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 197 By repeating the argument with the roles of G1 and G2 interchanged, we conclude that there is a permutation of G1, such that ¥>(01,02) = (¥1(01), ¥2(02)). Now, (*) implies that is a colour-permuting automorphism of Cay(G1; n^S)). Similarly, is a colour-permuting automorphism of Cay(G2; n2(S)). Since each Gi is CCA, we conclude that ^ is an automorphism of Gj. So ¥ is an automorphism of G1 x G2. □ The idea used in Example 2.4 yields the following result that generalizes the CCA part of Proposition 3.1. Proposition 3.3. Suppose G = H x K is a semidirect product, and Cay(H; S0) is a connected Cayley graph of H, such that: • S0 is invariant under conjugation by every element of K, and • there is a colour-preserving automorphism ^o of Cay(H; S0), such that either o ¥0 is not affine, or o ¥>0(e) = e, and there exist s G S0 and k G K, such that ¥0(k-1sk) = k-1 ¥0(s) k. Then G is not CCA. Proof. Define ¥: G ^ G by y(hk) = y0(h) k. We claim that ¥ is a colour-preserving automorphism of Cay(G; S0 U K) that is not affine (so G is not CCA, as desired). For k1 G K, we have ¥>(hk k1) = ¥0(h) kk1 = <^(hk) k1, so ¥ preserves the colour of K-edges. Now consider some s G S0 and let ks = ksk-1 G S0. Then, since is colour preserving, we have ¥(hks) = ^(h ksk) = ¥0(h ks) k = (y>0(h) (ks)±1) k = y>0(h) ks±1 = y>(hk) s±1, so ¥ also preserves the colour of S0-edges. Hence, ¥ is colour-preserving. Now, suppose ¥ is affine. Then the restriction of ¥ to H is also affine, so, by assumption, we must have y(e) = e, so ¥ is an automorphism of G. Hence, for all s G S0 and k G K, we have ¥0(k-1sk) = ¥(k-1sk) = ^(k)-1 y(s) ¥(k) = k-1 y(s) k = k-1 ¥0(s) k. This contradicts the hypotheses of the proposition. □ Remark 3.4. Proposition 3.3 can be generalized slightly: assume G = HK and H < G (but do not assume H n K = {e}, which would make G a semidirect product). Then the above proof applies if we make the additional assumption that ¥0(hk) = y0(h) k for all h G H and k G H n K. 198 Ars Math. Contemp. 11 (2016) 147-156 4 Abelian groups The following result shows that all non-CCA abelian groups can be constructed from examples that we have already seen in Corollary 2.8 (and that CCA and strongly CCA are equivalent for abelian groups). Proposition 4.1. For an abelian group G, the following are equivalent: 1. G has a direct factor that is isomorphic to either Z4 x Z2 or a group of the form Z2k x Z2 x Z2, with k > 3. 2. G is not CCA. 3. G is not strongly CCA. Proof. (1 ^ 2) This is immediate from Corollary 2.8 and Proposition 3.1. (2 ^ 3) Obvious. (3 ^ 1) Let be a colour-permuting automorphism of any connected Cayley graph Cay(G; S) on G, such that y(0) = 0. From Proposition 3.2 (and the fact that any abelian group is the direct sum of its Sylow subgroups), we may assume G is a p-group for some prime p. Then G == Zpfc^ X Z„k2 x • • • x Zpkm, with ki > k2 > • • • > km > 1. Since S is a generating set, it is easy to see that there is some s1 G S, such that |s11 = pkl. 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 on i, we see that there exist s1,..., sm G S, such that if we let Gj = (s1,..., sj), then Gj = Gi-1 x Zpfci and G = Gj x Zpki+1 x • • • x Zpkm, for each i. It is important to note that each element of Gj can be written uniquely in the form g + rsj, with g G Gj-i and -pki/2 < r < pki/2 (and r G Z). (f) For convenience, also let tj = (pfci sj) = pkitj. This implies that if we define a: Gj ^ Hj by a(g + rsj) = ^(g) + rtj for g G Gj-1 and r G Z, A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 199 then a is a well-defined isomorphism. So we need only show that the restriction of ^ to G» is equal to a (unless G has a direct summand of the desired form). Suppose y|Gi = a. (This will lead either to a contradiction or to a summand of the desired form.) Since ^ is colour-permuting and, by definition, a agrees with ^ on Gi-:, this implies there is some g G Gi-:, such that y(g + sj) = a(g + sj). However, since ^ is colour-permuting, we know <^(g + s») = <^(g) ± <£>(s») = a(g) ± t». Since a(g + s») = a(g) +tj, the preceding two sentences imply ¥>(g + s») = a(g) - t» G H»-i - t». Furthermore, since ^ is colour-permuting (and y(sj) = tj), we know that it maps edges of colour {s±:},..., {s±11} to edges of colour {t±:},..., {t±-11}, so ^(x + h) G ^(x) + H»-1 for all x G G and h G H»-1. Taking x = s» and h = g yields <^(g + s») G H»-1 + <^(s») = H»-1 + t». This contradicts the uniqueness of r in the analogue of (f) for H», unless 1 = pki/2. Hence, we must have pki = 2 (so Z2 is a direct summand of G), which means p = 2 and k» = 1. We have y(g) + 2t» = a(g + 2s») (definition of a) = y(g + 2s») (g + 2s» = g + pkis» G G»-1) = ¥>(g) - 2t» (y(g + s») = a(g) - t» = <^(g) - t»), so 4t» = 0. Also note that, since ¥>(g) + t» = a(g + s») = ^(g + s») = y(g) - t», we must have 2ti = 0. So |ti| = 4. Since (s1;..., s»-1) = G»-1, there must exist g' G G»-1, and j < i, such that ¥>(g' + s») = a(g') + t», but ^(g' + sj + s») = a(g' + sj) - t» = a(g') + tj - t». Since ^ is colour-permuting, we also have y(g' + sj + s») = ^(g' + s») ± tj = a(g') + t» ± tj. Hence, tj - t» = t» ± tj, so tj ^ tj = 2t». Since 2t» = 0, we conclude that 2tj = 2t»; hence, |tj | =4. Since 2kj = |Hj : Hj-11 is a divisor of |tj |, and |tj | = 4, there are two possibilities for kj: • If kj = 2, then Z4 x Z2 = Z2kj x Z^ is a direct summand of G, as desired. • If kj = 1, then, since |tj | = 4, there must be some I < j, such that k^ > 2. This implies that Z2k£ x Z2 x Z2 = Z2k£ x Z2kj x Z^ is a direct summand of G, as desired. □ Corollary 4.2. For n G Z+, there is a non-CCA abelian group of order n if and only if n is divisible by 8. 200 Ars Math. Contemp. 11 (2016) 147-156 5 Generalized dihedral groups Definition 5.1. The generalized dihedral group over an abelian group A is the group (a, A | a2 = e, aaa = a-1 Va G A}. Lemma 5.2. Suppose D is the generalized dihedral group over an abelian group A, and f is a colour-permuting automorphism of a connected Cayley graph Cay(D; S), such that f (e) = e. If A is strongly CCA, and f (S n A) = S n A, then f is an automorphism of D. Proof. Label the elements of S as S = {a1; a2,..., ak, a1; a2,..., at}, where aj G A for 1 < i < k, and aj G A for 1 < i < t (so each aj is an involution that inverts the elements of A). By assumption, {a1; a2,..., ak} and {a1; a2,..., at} are invariant under f. Thus, for each i, we have • f (aj) = aj for some aj G {a1; a2,..., ak}, and • f (aj) = a' for some a' G {a1; a2,..., at}. Notice that since a1,..., at are involutions, each aj is its own inverse. Therefore, whenever a is a word in a1,..., at and g G D, the fact that f is a colour-permuting automorphism means that f (ga) = f (g)a', where a' is formed from a by replacing each instance of aj in a by a'. Therefore, if we let E be the subgroup generated by {a1;..., at}, then f is a colour-preserving automorphism of the Cayley graph Cay(D; S U E). Hence, there is no harm in assuming that S = S U E, so E C S. Since (S n A} is normal in D (in fact, every subgroup of A is normal, because every element of D either centralizes or inverts it), we have D = (S n A}E. Therefore A = (SnA} (EnA) = (SnA}, so Cay(A; SnA) is connected. Since f is colour-preserving, and f (S n A) = S n A, this implies that f (A) = A. So f is a colour-permuting automorphism of the connected Cayley graph Cay(A; S n A). Since, by assumption, A is strongly CCA, this implies that f |A is an automorphism of A. So f (abe) = f (a) f (b)e for all a, b G A and e G Z. Now we are ready to show that f is an automorphism of D. Let g, h G D. Then we may write g = aa and h = ba, where a, b G A and a, a G {e, a1}. For convenience, let e G {±1}, such that aca = ce for all c G A. Note that, since a' G {a1;..., at}, we know that a1 and a1 both invert A, so we also have a'ca' = ce. Then f (gh) = f (aa • ba) = f (abe • aa) = f (a) f (b)e • a'a' = f (a)a' • f (b)a' = f (g) • f (h). Since g, h G D are arbitrary, this proves that f is an automorphism of D. □ Proposition 5.3. The generalized dihedral group D over an abelian group A is CCA if and only if A is CCA. Proof. Note that if f is any colour-preserving automorphism of a connected Cayley graph Cay(D; S), then f (S n A) = S n A, since A is closed under inverses. Furthermore, A is strongly CCA, since it is assumed to be CCA and every CCA abelian group is strongly CCA (see Proposition 4.1). Therefore, Lemma 5.2 implies that f is a group automorphism. So D is CCA. Write D = A x (a}. Since A is not CCA, there is a colour-preserving automorphism f 0 of some connected Cayley graph Cay(A; S), such that f 0 is not affine. Since A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 201 a inverts every element of S, it is easy to see that Cay(D; S U {a}) is isomorphic to the Cartesian product Cay(A; S) □ P2. So the proof of Proposition 3.1 provides a colour-preserving automorphism ^ of Cay(D; S U {a}) whose restriction to A is y>0, which is not an affine map. Therefore, ^ is not affine. □ The following result is the special case where A is cyclic (since Proposition 4.1 implies that every cyclic group is CCA). Corollary 5.4. Every dihedral group is CCA. Lemma 5.5. If T is a generating set of a group H, and a is a nontrivial automorphism of H, such that a(t) G {t±1} for every t G T, then the group G = (H x (a}) x Z2 is not strongly CCA. Proof. Let G' = H x Z2 x Z2 and define ^: G ^ G' by ax,y) = (h, x,y) for h G H and x, y G Z2. Since a(t) G {t±1} for every t, it is easy to verify that ^ is a colour-respecting isomorphism from Cay(G; (H, e, 0) U {(e, a, 0), (e, 0,1)}) to Cay(G; (H, 0, 0) U {(e, 1, 0), (e, 0,1)}). Permuting the two Z2 factors of G' provides an automorphism of G' that preserves the generating set, and therefore corresponds to a colour-permuting automorphism of the two Cayley graphs. However, it is not an automorphism of G, since it takes the central element (e, e, 1) to (e, a, 0), which is not central (since the automorphism a is nontrivial). □ Proposition 5.6. The generalized dihedral group over an abelian group A is strongly CCA if and only if either A does not have Z2 as a direct factor, or A is an elementary abelian 2-group (in which case, the generalized dihedral group is also an elementary abelian 2-group). Proof. Suppose A = A' x Z2, and A' is not elementary abelian. Then the generalized dihedral group A x (a} over A is isomorphic to (A' x (a}) x Z2, so Lemma 5.5 tells us that it is not strongly CCA. Let D = A x (a} be the generalized dihedral group over A, and let ^ be a colour-permuting automorphism of a connected Cayley graph Cay(D; S), such that y(e) = e. We may assume A does not have Z2 as a direct factor (otherwise, the desired conclusion follows from the fact that every elementary abelian 2-group is strongly CCA (see Proposition 4.1)). From Proposition 4.1, we see that A is strongly CCA. Hence, the desired conclusion will follow from Lemma 5.2 if we show that y(S n A) = S n A. Let a G S n A. Since ^ is colour-permuting, we have |y(s)| = |s| for all s G S. Also, we know that |g| = 2 for all g G D \ A. Therefore, it is obvious that y(a) G S n A if |a| = 2. So we may assume |a| = 2. Since A does not have Z2 as a direct factor, this implies that a is a square in A: that is, we have a = x2, for some x G A. Also, since Cay(D; S) is connected, we may write x = s1s2 • • • sn for some s1,..., sn G S. So a = (s1s2 • • • sn)2 can be written as a word in which every element of S occurs an even number of times. Since ^ is colour-permuting, this implies that y(a) can be written as a word in which, for each s g S, the total number of occurrences of either s or s-1 is even. Since s and s-1 both either centralize A or invert it, this implies that <^(a) centralizes A. Since every element of D \ A inverts A, we conclude that y(a) G A, as desired. □ 202 Ars Math. Contemp. 11 (2016) 147-156 6 Groups of odd order The following notation will be assumed throughout this section. Notation 6.1. For a fixed Cayley graph Cay(G; S): • A° is the group of all colour-preserving automorphisms of Cay(G; S). • G is the subgroup of A0 consisting of all left translations by elements of G. (Although we do not need this terminology, it is often called the left regular representation of G.) • He is the stabilizer of the identity element e in Cay(G; S), for any subgroup H of A0. Remark 6.2. It is well known (and very easy to prove) that a permutation of G is affine if and only if it normalizes G (see, for example [10, Lem. 2]). Lemma 6.3. A° is a 2-group. Proof. Let p G A°, so p is a colour-preserving automorphism of Cay(G; S) that fixes e. If C is any monochromatic cycle through e, then either p is the identity on C or p reverses the orientation of C. Therefore, p2 acts trivially on the union of all monochromatic cycles that contain e. This implies that p2 acts trivially on all vertices at distance < 1 from e. ok Repeating the argument shows that p2 acts trivially on all vertices at distance < k — 1 ok from e. For k larger than the diameter of Cay(G; S), this implies that p2 is trivial. So the order of p is a power of 2. □ Proposition 6.4. Let Cay(G; S) be a connected Cayley graph on a group G of odd order. If every colour-preserving automorphism of Cay(G; S) is affine, then every colour-permuting automorphism is affine. Proof. Let A* be the group of all colour-permuting automorphisms of Cay(G; S). Since A* acts on the set of colours, and A° is the kernel of this action (and the kernel of a homomorphism is always normal), it is obvious that A° < A*. Also, since G is CCA, we have G < A° (cf. Remark 6.2). Furthermore, |G| is odd, |A° | is a power of 2, and A° = G • A°. Therefore, G is the (unique) largest normal subgroup of odd order in A°. The uniqueness implies that G is characteristic in A°. (That is, it is fixed by all automorphisms of A°.) So G is a characteristic subgroup of the normal subgroup A° of A*. 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]. Therefore G < A*. This implies that G is strongly CCA (see Remark 6.2). □ Wreath products Zm^Z„ provide examples of non-CCA groups of odd order (see Example 2.4). We will see in Theorem 6.8 that the following slightly more general construction is essential for understanding many of the other non-CCA groups of odd order. Example 6.5. Let a be an automorphism of a group A, and let n G Z+. Then we can define an automorphism a of An by a(wi,. .. ,w„) = (a(wn),w1,w2,. .. , w„_i). A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 203 It is easy to see that the order of a is n times the order of a, so we may form the corresponding semidirect product An x ^Zn | a |. Let us call this the semi-wreathed product of A by Zn, with respect to the automorphism a, and denote it A la Zn. (If a is the trivial automorphism, then this is the usual wreath product A I Zn.) Negating the first coordinate, as in Example 2.4, shows that if n > 1 and A is abelian, but not an elementary abelian 2-group, then A la Zn is 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 Example 6.5 must contain a subgroup that is isomorphic to a semi-wreathed product A ia Zq, where A is an elementary abelian p-group, p and q are primes (not necessarily distinct), a is an automorphism of q-power order, and no nontrivial, proper subgroup of A is invariant under a. Definition 6.7 ([4, p. 5]). Let G be a group. For any subgroups H and K of G, such that K < H, the quotient H/K is said to be a section of G. Theorem 6.8. Any non-CCA group of odd order has a section that is isomorphic to either: 1. a semi-wreathed product A la Zn (see Example 6.5), where A is a nontrivial, elementary abelian group (of odd order) and n > 1, or 2. the (unique) nonabelian group of order 21. Proof. Assume Cay(G; S) is a connected Cayley graph on a group G of odd order that does not have a section as described in either (1) or (2). We will show, by induction on the order, that if A is any subgroup of A0 that contains G, then G is a normal subgroup of A. (Then taking A = A0 implies that G is CCA (see Remark 6.2).) It is important to note that this conclusion implies G is a characteristic subgroup of A (because Lemma 6.3 implies that G is the unique largest normal subgroup of odd order). For convenience, we write G < A when G is characteristic. Let N be a minimal normal subgroup of A. Then N is 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. Assume N is elementary abelian. Since the Sylow 2-subgroup Ae, being the stabilizer of a vertex, does not contain any normal subgroups of A, we know that N is not contained in a Sylow 2-subgroup. Hence, N is not a 2-group, so it must be a p-group for some odd prime p. Therefore, since G is a maximal subgroup of odd order, we have N C G, so N = N, for some (elementary abelian) normal subgroup N of G. Let N+ be the largest normal subgroup of A that is contained in NAe. Since NAe is the stabilizer of a point under the action of A on the space G/N of N-orbits, we know that N+ is the kernel of the action of A on G/N, so A/N+ is a group of colour-preserving automorphisms of Cay(G/N; S), where S is the image of S in G/N.. Therefore, by induction on |A|, we know that GN+/N+ is normal in A/N+, so GN+ is normal in A. Then we may assume Gn+ = A, for otherwise, by induction on |A|, we would know G < Gn+, so G < A, as desired. Since |G| is odd, this implies that N+ contains a Sylow 2-subgroup of A. In fact, since N+ is normal and all Sylow 2-subgroups are conjugate, this 204 Ars Math. Contemp. 11 (2016) 147-156 implies that N+ contains every Sylow 2-subgroup. In particular, it contains Ae. Therefore N+ = NAe, so NAe < A. This means that Ae acts trivially on G/N, so, for every s G S \ N, Ae preserves the orientation of every s-edge. (This uses the fact that, since |s | is odd, s ^ s-1 (mod N) if s G N.) This implies: for ^ G Ae, g G G, and x G (S \ N}, we have y(gx) = ^(g) x. (6.9) Let (S n N) = { gsg-1 | s G S n N, g G (S \ N} }. Now, suppose t G (SnN) and h G N. There exists s G SnN and x G (S \ N}, such that xsx-1 = t. From (6.9) and the fact that ^ is colour-preserving, we see that y(ht) = ^(hxsx-1) = y(h) x s±1x-1 = <^(h) t^1. Hence, is a colour-preserving automorphism of Cay(V; (S n N) U ((S \ N} n N)). Since S generates G, it is easy to see that this Cayley graph is connected. Note that CAe (N) is normalized by both N and Ae, so it is a normal subgroup of NAe. Therefore, it must be trivial (since the largest normal 2-subgroup of NAe is characteristic, and is therefore normal in A, but the stabilizer Ae does not contain any nontrivial normal subgroups of A). So Ae acts faithfully by conjugation on N. (6.10) Also, we know that is an automorphism of N (by Remark 6.2, since ^ normalizes N = N). Since, being a colour-preserving automorphism, ^ either centralizes or inverts every element of the generating set of N, this implies that is trivial. Since this is true for every ^ G Ae, we conclude that Ae acts on N via an elementary abelian 2-group. From (6.10), we conclude that Ae is elementary abelian. We can think of N as a vector space over Zp, and, for each homomorphism 7: A ^ {±1}, let Ny = { n G N | ana-1 = 7(a) n for all a G Ae }. (This is called the "weight space" associated to 7.) Since every linear transformation satisfying T2 = I is diagonalizable, and Ae is commutative, the elements of Ae can be simultaneously diagonalized. This means that if we let r — {7 | N^ = {0} }, then, since eigenspaces for different eigenvalues are always linearly independent, we have N = 07er Ny. This direct-sum decomposition is canonically defined from the action of Ae on N. Since G acts on NAe (by conjugation), we conclude that the action of G on N by conjugation must permute the weight spaces. More precisely, there is an action of G on r, such that VN7V-1 = Ng7 for all g G G. Since N is abelian, this factors through to a well-defined action of G/N on r. If the G-action on r is trivial, then every weight space is G-invariant, which implies that the action ^f G on N commutes with the ^ction of Ae. Sjnce Ae acts faithfully, we conclude that G centralizes AeN/N; that is, [G, Ae] C N C G. So Ae normalizes G, as desired. A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 205 We may now assume that the G-action is nontrivial, so there is some g G G with an orbit of some length n > 1 on r. Let 70 be an element of this orbit, so gn normalizes NYo. Since S \ N generates G/N, we may assume g G S \ N, so (6.9) tells us that (?) n N is centralized by Ae. However, the minimality of N implies that CN(Ae) = N n Z(NAe) is trivial. Therefore, (N, g) = N x (?) is a semidirect product. So (Nyo,?) = (0 PM N7) x (g). Then modding out C^ (NYo ) yields a section of G that is isomorphic to NYo \a Zn, where a is the automorphism of NYo induced by the conjugation action of g™. So G has a semi-wreathed section, as described in (1). This completes the proof of this case. Case 2. Assume N = £1 x • • • x Lr, where each Li is a nonabelian simple group, and Li = L1 for all i. We know that A = GAe, Ae is a 2-group, and |G| is odd, so G is a 2-complement in A. (By definition, this means that |G| is odd and |A : G| is a power of 2 [6, p. 88].) So L1 is a nonabelian simple group that has a 2-complement (namely, G n L1). By using the Classification of Finite Simple Groups, it can be shown that this implies L1 = PSL(2,p), for some Mersenne prime p > 7 (see [8, Thm. 1.3]). Note that Ae n Li is a Sylow 2-subgroup of PSL(2,p). Therefore, it is dihedral [4, Lem. 15.1.1(iii)] and has order p +1 (because p is a Mersenne prime). Let • Ci be the unique cyclic subgroup of order (p + 1)/2 in Ae n Li, • C2 be the unique subgroup of index 2 in Ci, and • e2 = e? x • • • e2 c Ae n (l1 x • • • x Lr). Since every element of ei is a colour-preserving automorphism, it either fixes or inverts each element of S, so we know that C2 fixes every element of S. Since stabilizers are conjugate, this implies s-1 e2g C Ae, for every s G S. We must have p > 7, for otherwise G n Li, being the 2-complement of PSL(2, 7), would be the nonabelian group of order 21, as in (2). This implies that C2 is the unique cyclic subgroup of order (p + 1)/4 in the dihedral group Ae n Li, so we must have s- 1e2g = C2, which means that Snormalizes C2. Since this holds for every s in the generating set S, we conclude that G normalizes C2. Note that Ae normalizes Ae n N, and that C2 < Ae n N (since, as was mentioned above, Ci is the unique cyclic subgroup of its order in Ae n Li). Therefore, C2 < Ae. We conclude that C2 is normal in G?Ae = A. So C2 = C2 n L1 is normal in L1, contradicting the fact that L1 is simple. □ Lemma 6.11. To prove a group G is strongly CCA (or CCA), it suffices to consider only the connected Cayley graphs Cay(G; S), such that every element of S has prime-power order. Proof. Suppose ^ is a colour-permuting automorphism of some connected Cayley graph Cay(G; S). There is a permutation n of S, such that y(gs) = y(g) n(s)±1, for all g G G and s G S. (Furthermore, if ^ is colour-preserving, then n can be taken to be the identity permutation.) By induction on k, this implies ^(gsfc) = y>(g) n(s)±k, for all k G Z. Hence, if we let S* = { sk | s G S, k G Z }, then ^ is a colour-permuting automorphism of Cay(G; S*). Now, let S0 = {t G S* | |t| is a prime-power }. 206 Ars Math. Contemp. 11 (2016) 147-156 Then ^ is a colour-permuting automorphism of Cay(G; S0), and S0 generates G, since every element s of the generating set S can be written as a product of elements of (s} that have prime-power order [4, Thm. 1.3.1(iii), p. 9], and therefore belong to S0. (Furthermore, ^ is colour-preserving if the permutation n is the identity permutation.) □ Lemma 6.12. Suppose • C is a cyclic, normal subgroup of a group H, • |C| is relatively prime to |H : C|, • no element of H \ C centralizes C, and • a is any automorphism of H. Then a(h) € hC,for every h € H. Proof. Since no other subgroup of H has the same order as C, we know that a|C is an automorphism of C, so there exists r € Z, such that a(c) = cr, for every c € C. Then, for any h € H and c € C, we have a(h) cr a(h)-1 = a(h) a(c) a(h)-1 = a(hch-1) = (hch-1)r = hcrh-1, so h-1 a(h) centralizes C. By assumption, this implies h-1 a(h) € C, as desired. □ Corollary 6.13. The following are equivalent: 1. There is a group of order n that is not CCA. 2. There is a group of order n that is not strongly CCA. 3. n > 8, and n is divisible by either 4, 21, or a number of the form pq • q, where p and q are primes (not necessarily distinct) and p is odd. Proof. We prove (1 ^ 3) and (1 ^ 2). (3 ^ 1) If n is divisible by 4, then there is a generalized dicyclic group of order n, which is not CCA (see Corollary 2.8(4)). The nonabelian group of order 21 and the wreath product Zp I Zq (which is of order pq • q) are not CCA (see Examples 2.3 and 2.4). Taking an appropriate direct product yields a non-CCA group whose order is any multiple of these (see Proposition 3.1). (1 ^ 3) Assume there is a group G of order n that is not CCA, but n is not divisible by 4, 21, or a number of the form pq • q. From Theorem 6.8, we see that n is even. (Otherwise, n = |G| is divisible by the order of a semi-wreathed product | A ia Zk |. If we let p and q be prime divisors of |A| and k, respectively, then |A ia Zk| = |A|k • k is amultiple ofpq • q.) Furthermore, n must be square-free, for otherwise it is a multiple of either 4 or p2 • 2, for some prime p. Therefore, G is a semidirect product Zk x Z^. We may assume the centre of G is trivial, for otherwise we can write G as a nontrivial direct product, so Proposition 3.2 (and induction on n) implies that G is CCA. Therefore, k is odd (so I is even), so we may write G = Zk x (Zm x Z2), and Zm x Z2 acts faithfully on Zk. Let H = Zk x Zm, so |H | = km is odd, and H is the (unique) subgroup of index 2 in G. Let ^ be a colour-preserving automorphism of a connected Cayley graph Cay(G; S). (We wish to show that ^ is affine.) There is no harm in assuming that every element of S has prime order (see Lemma 6.11). Fix some t € S with |t| = 2. We claim we may assume that t is the only element of order 2 in S, and that H = (S \ {t}}. To see this, let A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 207 • T be the set of all elements of order 2 in S, and • S' = {t} U { uv | u, v G T, u = v } U (S \ T). It is easy to see that ^ is a colour-preserving automorphism of the connected Cayley graph Cay(G; S'), and that G = (S \ {t})(t}. This establishes the claims. From Theorem 6.8 (and the fact that |H| is odd), we know that is affine. By composing with a left translation, we may assume that ^ fixes e. Then is a group automorphism. By composing with an automorphism of Zk x (Zm x Z2) of the form (x, y, z) ^ (xr, y, z), we may assume is the identity map. Also, since <^(s) G {s±1} for every s G S, and |H/Zk| = m is odd, Lemma 6.12 implies that ^ also fixes every element of (S n H) \ Zk. Hence, is an automorphism that fixes every element of a generating set, so y(fc) = h for every h G H. Since y(ht) = ^(h) t = ht, for all h G H (because ^ is colour-preserving and t = t-1), we conclude that ^ fixes every element of G, and is therefore affine, as desired. (1 ^ 2) Obvious. (2 ^ 1) Assume there is a group G of order n that is not strongly CCA, but n is not divisible by 4, 21, or a number of the form pq ■ q. Let ^ be a colour-permuting automorphism of some connected Cayley graph Cay(G; S), such that y(e) = e. As in the proof of (1 ^ 3) above, we see that we may assume |G| is square-free, and we may write G = Zk x (Zm x Z2), where Zm x Z2 acts faithfully on Zk. Let H = Zk x Zm be the (unique) subgroup of index 2 in G. From (1 ^ 3) above, we know that G is CCA, so G < A0. Hence, H < A0 (since it is the unique largest normal subgroup of odd order), so ^ normalizes H. This implies that the restriction of ^ to H is an automorphism of H. For each s g S, let I = y(s) G S. To prove that ^ is affine, it suffices to show y(xs) = y(x) I for all x G G and s G S (see Remark 1.6(4)). If this is not the case, then, since ^ is colour-permuting, there must be some x, such that y(xs) = y(x) I-1 (and I-1 = I, which means |s| = 2). This will lead to a contradiction. We may assume every element of S has prime order (see Lemma 6.11). Since |s| = 2, this implies s G H. Then, since is an automorphism, but ^(xs) = <^(x) I-1 = y(x) <^>(s)-1 = y(x) y(s), we must have x G H. Since H has only two cosets, and there must be some element of S that is not in H, this implies that we may assume x G S, after multiplying on the left by an appropriate element of H (and using the fact that ^ normalizes H). Note that, since x G H, and every element of S has prime order, this implies |x| = 2. So the order of I is also 2, which implies xI / H (since | H| is odd). Since ^ is colour-permuting, we have ^(xs) = xsx) = xs)I. Also, by the choice of x and s, we have y(xs) = y(x) I-1 = 11-1. Therefore /x \ x—— 1 s) = s . Since Zm acts faithfully on Zk, we have a(h) = h (mod Zk), for every automorphism a of H (see Lemma 6.12). Since ^ and conjugation by x are automorphisms of H, this implies s = s-1 (mod Zk). Since |s| is odd, we conclude that s G Zk. 208 Ars Math. Contemp. 11 (2016) 147-156 Then, since the automorphism group of a cyclic group is abelian, we have 9(xs) = = so x-1x must invert J. But this is impossible, because, as was mentioned above, x and x, being of order 2, cannot be in H, so they are both in the other coset of H, so x-1x G H has odd order. This contradiction completes the proof that 9 is affine. □ Remark 6.14. It is not necessary to assume p is odd in the statement of Corollary 6.13(3), because 2q ■ q is divisible by 4, which is already in the list of divisors. Theorem 6.8 implies that very few small groups of odd order fail to be strongly CCA: Corollary 6.15. Let G21 = Z7 x Z3 be the (unique) nonabelian group of order 21. Then the only groups of odd order less than 100 that are not strongly CCA are G21, G21 x Z3, and Z3 I Z3. Proof. Suppose G is a group of odd order, such that G is not strongly CCA and |G| < 100. From Corollary 6.13, we see that |G| is divisible by either 21 or 33 ■ 3 = 81. Since |G| < 100, this implies that |G| is either 21, 21 x 3 = 63, or 33 ■ 3 = 81. Also, G must be nonabelian (see Corollary 4.2). • The nonabelian group G21 of order 21 is not CCA (see Example 2.3). • There are two nonabelian groups of order 63. One of them, the direct product G21 x Z3, is not CCA (see Proposition 3.1). • Theorem 6.8 implies that Z3 I Z3 is the only non-CCA group of order 81 (see also Example 2.4). To complete the proof, we sketch a verification that the following group of order 63 is CCA: G = Z7 x Z9 = (x, a | x7 = a9 = e, a-1xa = x2 }. Let 9 be a colour-preserving automorphism of a connected Cayley graph Cay(G; S), such that 9(e) = e. We may assume S is either {a±1, x±1} or {a±1, (ax)±1}, after discarding redundant generators, applying an automorphism of G, and replacing some elements by appropriate powers (cf. the proof of Lemma 6.11). If S = {a±1,x±1}, then we may assume (ga) = 9(g) ae for all g G G. Then, since (1,1) is the only pair (e, J) G {±1}2 that satisfies a-ex5ae = x2, we see that ^(xW) = x®aj for all i and j, so 9 is the identity map, which is certainly affine. Assume, now, that S = {a±1, (ax)±1}. Let a1 = a and a2 = xa. For any g G G and e G {±1}, if 9(ga1) = 9(g) af, then, since af = af (and 9 is colour-preserving), we have y(g sm) = 9(g) sem, for all m and all s G S. Since S generates G, this implies <9>(gs) = 9(g) se for all g and all s G S. So 9 is affine. □ A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 209 7 Groups of small order In this section, we briefly explain which groups of order less than 32 are CCA (or strongly CCA). First, note that almost all of the abelian ones are strongly CCA: Proposition 7.1 (cf. Proposition 4.1). An abelian group of order less than 32 is not strongly CCA if and only if it is either • Z2 x Z4 (of order 8), • Z2 x Z2 x Z4 (of order 16), or • Z2 x Z3 x Z4 (of order 24). None of these are CCA. Also note that almost all of the groups whose order is not divisible by 4 are CCA: Proposition 7.2. The only groups that are not strongly CCA, and whose order is < 32 and not divisible by 4 are: • the wreath product Z3 I Z2, which is isomorphic to D6 x Z3 and has order 18, and • the nonabelian group of order 21. Neither of these is CCA. Proof. For the groups of odd order, the conclusion is immediate from Theorem 6.8 and Example 2.3 (see Corollary 6.15 for a stronger result). Proposition 3.2 deals with the groups D6 x Z5 and D10 x Z3 of order 30. For all of the other groups of even order, it suffices to note that if m is odd, then every generalized dihedral group of order 2m is strongly CCA (see Proposition 5.6). □ So it is surprising that very few of the remaining groups are strongly CCA: Proposition 7.3. The only nonabelian groups that are strongly CCA and whose order is < 32 and divisible by 4 are: • the dihedral groups of order 8, 16, and 24, • the alternating group A4, which is of order 12, • another group of order 16, namely, the semidirect product Z8 x Z2 in which a-1xa = x5 for x G Z8 and (a) = Z2, and • three additional groups groups of order 24, namely, D8 x Z3, A4 x Z2, and the semidirect product Z3 x Z8 in which Z8 inverts Z3. Furthermore, the only groups of order < 32 that are CCA, but not strongly CCA, are: • the dihedral groups D12, D20, and D28, and • the group D12 x Z2, which is a generalized dihedral group of order 24. 210 Ars Math. Contemp. 11 (2016) 147-156 Sketch of proof. The result can be verified by an exhaustive computer search, but we summarize a case-by-case analysis that can be carried out by hand, using the classification of groups of order less than 32. Each group of such small order can be specified by its "GAP Id',' which is an ordered pair [n, k], where n is the order of the group, and k is the id number that has been assigned to that particular group (see [5], for example). Assume G is nonabelian, |G| < 32, and |G| is divisible by 4. We may assume that G is neither generalized dicyclic, semidihedral, nor generalized dihedral, for otherwise Corollary 2.8(4,5) and Propositions 5.3 and 5.6 determine whether G is CCA or strongly CCA. By inspection of the list of groups of each order, we see that this leaves only thirteen possibilities for G, and we consider each of these GAP Ids separately. In most cases, Proposition 2.5 implies that G is not CCA. [12, 3] = A4. This group is strongly CCA (see Example 7.5 below). [16, 3] = ( a, b, c | a4 = b2 = c2 = e, ab = ba, bc = cb, cac = ab}. Proposition 2.5 applies with S = {a±\ c}, T = {a^}, and t = a2 G Z(G). [16, 6] = ( a, x | a8 = x2 = e, xax = a5 } = (a} x (x} = Z8 x Z2. This group is strongly CCA (see Example 7.5 below). [16,13] = ( a, x, y | a4 = x2 = e, a2 = y2,xax = a-1, ay = ya, xy = yx}. Proposition 2.5 applies with S = {a±1,x,y±1}, T = {a±:, y±:}, and t = a2 G Z(G). [20, 3] = ( a, b | a5 = b4 = e, bab-1 = a2 }. Proposition 2.5 applies with S = {a±:, b±:}, T = {b±1}, and t = b2 (which inverts a). [24,1] = Z3 x Z8, where Z8 inverts Z3. This group is strongly CCA (see Example 7.5 below). [24, 3] = SL(2,3) = Q8 x Z3 = (i, j} x (a}, where aia-1 = j and a-1ia = ij. Proposition 2.5 applies with S = {¿±\ ai1}, T = {¿+1}, and t = i2 G Z(G). [24, 5] = S3 XZ4. Proposition 2.5 applies with T = {(1,2)}x{±1}, S = {((2, 3), 0)}uT, and t = (e, 2) G Z(G). [24, 8] = Z3 x D8 = ( a, b, c | a3 = b4 = c2 = e, bab-1 = a-1, ac = ca, cbc-1 = b-1}. Proposition 2.5 applies with S = {(ab)±1, b±1, c}, T = {(ab)±1, b±}, and t = b2 G Z(G). [24.10] = D8 x Z3. Since D8 is strongly CCA (see Proposition 5.6), the same is true for this group (see Proposition 3.2). [24.11] = Q8 x Z3. This is not CCA, since Q8 is not CCA (see Corollary 2.8(3) and Proposition 3.1). [24.12] = S4. Let a = (1,2, 3,4) and b = (1,2,4, 3), so Proposition 2.5 applies, with S = {a±1,b±1}, T = {a^1}, and t = a2 = (1,3)(2,4), which inverts b. [24.13] = A4 x Z2. This group is strongly CCA (see Example 7.5 below). □ The following simple observation plays a key role in the proof of Example 7.5. Lemma 7.4. Let • f be a colour-permuting automorphism of a Cayley graph Cay(G; S), such that ^(e) = e> A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 211 • a = ((a) andb = ((b), for some a,b G S, • t(v) G {±1}, such that ((va) = ((v) aT(v),forall v G G, and • k1,k2, ...,k2r e Z \ {0}, such that akl bk2 ak3 ■ ■■ = e (and r > 2). If e1 = e3 and e2 = e4, for all e1,..., e2r e {±1}, such that aeiklbe2k2 ■ ■ ■ be2rk2r = e, then <(va) = <(v) a and <(vb) = <(v) b, for all v e (ak3, bk2). Proof. Since < is colour-permuting, there exist a,r: G ^ {±1}, such that We wish to show a(v) = t(v) = 1 for all v e (ak3, bk2). Since a(e) = t(e) = 1, it suffices to show that a(vbk2) = t(vak3) = t(v) for all v e G. The two parts of the proof are very similar, so we show only that a(vbk2) = a(v). The relation akl bk2 ak3 ■ ■ ■ bk2r = e represents a closed walk starting at v (or at any other desired vertex). Applying < yields a closed walk starting at <(v). Since < is colour-permuting, this closed walk corresponds to a relation of the form a€lklb€2k2 ■ ■ ■ b€2rk2r = e, with ei e {±1}. By assumption, we must have e1 = e3. Therefore This establishes the desired conclusion, since a(v) = a(vakl), and vakl is an arbitrary Example 7.5. The groups [12,3], [16,6], [24,1], and [24,13] from the proof of Proposition 7.3 are strongly CCA. Proof. We consider each of the four groups individually; for convenience, let G be the group under consideration. Suppose ( is a colour-permuting automorphism of a connected Cayley graph Cay(G; S), such that ((e) = e, and let I = ((s), for each s G S. We wish to show ( G Aut G. Assume G = [12, 3]. Let a G S with |a| = 3, and let N be the (unique) subgroup of order 4 in G. Assume, for the moment, that there exists b G S n N (so |b| = 2). Then (ab)3 = e. Suppose i, j, k G {±1}, with so i + j + k = 0 (mod 3). Since i, j, k e {±1}, this implies i = j = k. We conclude from Lemma 7.4 that <(vs) = <(v) a for all v e (a, b) = G and s e {a±1,b}, so < e Aut G. We may now assume |s| = 3 for all s e S. Let b e S \ (a). We may assume a = b (mod N), by replacing b with its inverse if necessary. Write b = arx, with r e {±1} and x e N. Note that (a-1b)2 = e. Suppose i,j, k,i e {±1}, with ((va) = ((v) Ia(v) and ((va) = ((v) bT(v) for all v G G. a(akl bk2 ) = e3 = = a(v). element of G. □ e = 7jb IP b Ikb = ai+j+k (mod N), (Ik-rexl-k+r£)x if j = i =1, (IkxI-k )x if j = —1 and i = 1, I-t£ (akxl-k )xari if j = 1 and i = —1, (Ik-rp xI-k+rj )xIre if j = i = —1. 212 Ars Math. Contemp. 11 (2016) 147-156 Since the component in N must be trivial, and no nontrivial power of a centralizes x, we see that we must have j = I and k = rj = r£. Then, since the exponent of a must be 0, this implies i = k. We conclude from Lemma 7.4 that f (vs) = f (v) a, for all v G (a, 6} = G and s G {a± so f G Aut G. Assume G = [16, 6]. Let a G S with |a| = 8. Let 6 G S \ (a}. Assume, for the moment, that |6| = 8. Write 62 = a2r, for some odd r. Then we must have 62 = a2r. This implies that if i, j G {±1}, such that e = a2® a-2rj, then i = j (since |62| = |62| > 2). We conclude (much as in Lemma 7.4) that f (vs) = f (v) a, for all v G (a, 6} = G and s G {a±1,6±1}, so f G Aut G. We may now assume |6| G {2,4}, so 62 G (a4}. Note that, since 6 G (a}, we have 6a6-1a3 = e. Suppose i, j, k, I G {±1}, with e = 6®a?6-ka3* = 6i-ka5j+3* = aj-* (mod (a4}), so j = I. Then we must also have i = k. We conclude from Lemma 7.4 that f (vs) = f (v) a, for all v G (a, 6} = G and s G {a±1,6±1}, so f G Aut G. Assume G = [24,1]. Let a G S with |a| = 8, and let 6 G S, such that 6 G (a}. Write 6 = arx, where (x} = Z3. We may assume 6 has prime-power order (see Lemma 6.11), and we know that a2 centralizes x, so either r is odd or r = 0. Assume, for the moment, that r = 0, which means (6} = Z3 = (6}. Then a inverts 6, so a6a-16 = e. Suppose i, j, k, £ G {±1}, with e = a v a-k a* = ai-k 6-j+*. Since the exponents of a and 6 must be 0, we have i = k and j = We conclude from Lemma 7.4 that f (vs) = f (v) a, for all v G (a, 6} = G and s G {a±1, 6±1}, so f G Aut G. We may now assume that r is odd. The proof of Lemma 6.11 shows there is no harm in replacing 6 with a power that is relatively prime to 8, so we may assume r = 1. Since a2 G Z(G), we have a26a-26-1 = e. Suppose i, j, k, I G {±1}, with e = a2iV a-2k = a2i-2k P-* = (mod (a4, x}). Then j = Therefore a2i-2k = e, so i = k. For v G G with f(va) = f(v) a, we conclude from the proof of Lemma 7.4 that f (v6a) = f (v6) a. In addition, interchanging the roles of a and 6 tells us that if f (v6) = f (v) 6, then f (va6) = f (va) 6. We conclude that f (vs) = f (v) a, for all v G (a, 6} = G and s G {a±1, 6±1}, so f G Aut G. Assume G = [24,13]. We may assume |s| G {2,3}, for all s G S (see Lemma 6.11). Let a G S with |a| = 3. Choose 6 G S, such that 6 G A4. Since every element of order 3 is contained in A4, we must have |6| =2. Assume, for the moment, that (a, 6} = G. Note that (a6a-16)2 = e, and, for convenience, let 6m = a-m 6 am for m G Z. Suppose i, j, k, £ G {±1}, with e = a® 6 a-j 6 ak 6 a-* 6 = ai-j+k-* • 6_j+k-* 6k-* 6_* 6. A. Hujdurovic et al.: On colour-preserving automorphisms of Cayley graphs 213 This implies k = i, for otherwise 0, —i, and k — i are all distinct modulo 3, so bk_e b_ b = b1b_1b = e (mod Z2), but b_j+k_e is obviously nontrivial (mod Z2). (Then, since the exponent of a is 0, we must also have i = j.) We conclude from Lemma 7.4 that p(vs) = p(v) for all v G (a, b) = G and s G {a±1, b}, so p G Aut G. We may now assume (a, s) = G, for all s G S. Then, since b G A4 (and b is an element of order 2 in S), we see that b G Z(G). Since Z(G) has only one nontrivial element, this implies that S = (S n A4) U {b}, and that b = b (since only b-edges make 4-cycles with the edges of every other colour). Therefore Cay(G; S) = Cay(A4; S n A4) x Cay(Z2; {b}), and p(b) = b. Since A4 is strongly CCA, it is now easy to see that p G Aut G. □ Acknowledgments. D. W. M. and J.M. thank the Faculty of Mathematics, Natural Sciences and Information Technologies of the University of Primorska (Slovenia) for its hospitality during the visit that gave rise to this research project. References [1] M. Albert, J. Bratz, P. Cahn, T. Fargus, N. Haber, E. McMahon, J. Smith and S. Tekansik, Color-permuting automorphisms of Cayley graphs. Congr. Numer. 190 (2008), 161-171. MR2489799 [2] E. Dobson, Some non-normal Cayley digraphs of the generalized quaternion group of certain orders, Electron. J. Combin. 10 (2003), #R31, 7 pages. MR 2014518 [3] M. L. Fiol, M. A. Fiol and J. L. A. Yebra, When the arc-colored line digraph of a Cayley colored digraph is again a Cayley colored digraph, Ars Combin. 34 (1992), 65-73. MR 1206550 [4] D. Gorenstein, Finite Groups, second ed., Chelsea, New York, 1980. ISBN 0-8284-0301-5, MR0569209 [5] Groupprops, The Group Properties Wiki: Groups of a particular order, http://groupprops.subwiM.org/wiki/Category:Groups_of_a_particular_order [6] I. M. Isaacs, Finite Group Theory, American Mathematical Society, Providence, RI, 2008. ISBN 978-0-8218-4344-4, MR 2426855 [7] C. H. Li, On isomorphisms of finite Cayley graphs—a survey, Discrete Math. 256 (2002) 301334. MR 1927074 [8] C. Martinez-Perez and W. Willems, The trivial intersection problem for characters of principal indecomposable modules, Adv. Math. 222 (2009), 1197-1219. MR 2554934 [9] J.Morris, Automorphisms of circulants that respect partitions, Contrib. Discrete Math. (to appear). [10] S. K. Sehgal, On the normalizer of a group in the Cayley representation, Internat. J. Math. Math. Sci. 12 (1989), 459-462. MR 1007196 [11] A. T. White, Graphs, Groups and Surfaces, Elsevier, New York, 1973. MR 0340026 [12] M.-Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182 (1998), 309-319. MR 1603719