Colour-permuting and colour-preserving automorphisms
Joy Morris
University of Lethbridge, Canada
Ademir Hujdurovic
University of Primorska
Klavdija Kutnar
University of Primorska
Dave Witte Morris
University of Lethbridge
PDF
PLENARY TALK
Content: A Cayley graph Cay$(G;S)$ on a group $G$ with connection set $S=S^{-1}$ is the graph whose vertices are the elements of $G$, with $g \sim h$ if and only if $g^{-1}h \in S$. If we assign a colour $c(s)$ to each $s \in S$ so that $c(s)=c(s^{-1})$ and $c(s)\neq c(s')$ when $s' \neq s, s^{-1}$, this is a natural (but not proper) edge-colouring of the Cayley graph. The most natural automorphisms of any Cayley graph are those that come directly from the group structure: left-multiplication by any element of $G$; and group automorphisms of $G$ that fix $S$ setwise. It is easy to see that these graph automorphisms either preserve or permute the colours in the natural edge-colouring defined above. Conversely, we can ask: if a graph automorphism preserves or permutes the colours in this natural edge colouring, need it come from the group structure in one of these ways? We show that in general, the answer to this question is no. We explore the answer to this question for a variety of families of groups and of Cayley graphs on these groups. I will touch on work by other authors that explores similar questions coming from closely-related colourings.