Lethbridge Number Theory and Combinatorics Seminar: Joy Morris

A Cayley graph Cay(G;S) on a group G with connection set S (closed under inverses) is the graph whose vertices are the elements of G, with g adjacent to h if and only if h is in gS. If we assign a colour c(s) to each s in S so that the inverse of s has the same colour as s but other elements of S have different colours, 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 two ways?

I will show that in general, the answer to this question is no. I will 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.

This is based on joint work with Ademir Hujdurovic, Klavdija Kutnar, and Dave Witte Morris.