Colour-permuting automorphisms of complete Cayley graphs

Abstract

Let $G$ be a (finite or infinite) group, and let $K_G=\mathrm{Cay}(G;G\setminus \{1\})$ be the complete graph with vertex set $G$, considered as a Cayley graph of $G$. Being a Cayley graph, it has a natural edge-colouring by sets of the form $\{s,s^{-1}\}$ for $s\in G$. We prove that every colour-permuting automorphism of $K_G$ is an affine map, unless $G\cong Q_8\times B$, where $Q_8$ is the quaternion group of order $8$, and $B$ is an abelian group, such that $b^2$ is trivial for all $b\in B$. We also prove (without any restriction on $G$) that every colour-permuting automorphism of $K_G$ is the composition of a group automorphism and a colour-preserving graph automorphism. This was conjectured by D. P. Byrne, M. J. Donner, and T. Q. Sibley in 2013.

16 pages, no figures. Version 2 corrected a formatting error in the arxiv abstract