Colour-permuting automorphisms of Cayley graphs

Abstract

A Cayley graph is a certain graph constructed from a group and a generating set. It has a natural edge-colouring that specifies the generators corresponding to each edge. An automorphism of a Cayley graph is colour-preserving if it preserves each colour class of edges, and colour-permuting if it permutes the colour classes. A Cayley graph is called CCA if every colour-preserving automorphism is affine, and strongly CCA if every colour-permuting automorphism is affine. The main goal of this thesis is to study colour-preserving automorphisms and colour-permuting automorphisms of Cayley graphs, with particular emphasis on abelian groups and complete Cayley graphs.

For connected Cayley graphs on abelian groups, we prove that non-affine behaviour can occur only in the presence of a specific configuration of elements of order 4 in the connection set. Using local permutations induced by colour-permuting automorphisms, we obtain a complete characterization of connected abelian Cayley graphs that are CCA, and show that they are strongly CCA. Specifically, for a connected Cayley graph Cay(G; S) on an abelian group G, the graph is strongly CCA if and only if

|G : ⟨{2s} ∪ {t ∈ S | 2t ≠ 2s}⟩| ≤ 2

for every element s ∈ S of order 4. As a consequence, we obtain a complete classification of non-CCA connected two-generator abelian Cayley graphs.

We also study graphical regular representations (GRRs), Cayley indices, and normal Cayley graphs. We give a proof of the known fact that elementary abelian 2-groups admit a GRR exactly when their rank is not 2, 3, or 4. We also verify the Cayley indices of all finite groups and correct some previously published connection sets for certain generalized dicyclic groups. Using these results, we obtain an alternative proof of the classification of finite groups that admit a normal Cayley graph.

Finally, we prove that the complete Cayley graph K_G is strongly CCA unless G ≅ Q_8 × B, where Q_8 is the quaternion group of order 8, and B is an abelian group of exponent 2. We also prove that every colour-permuting automorphism of a complete Cayley graph is the composition of a group automorphism and a colour-preserving automorphism.