Home > Timetable > Contribution details


Automorphisms that preserve the natural edge-colouring


  • Joy MORRIS

Primary authors



A major topic of research in symmetries of graphs is that of finding graphs that admit specific sorts of automorphisms, but do not admit other automorphisms. The study of regular representations is an example of this. Another way to approach this topic is to ask what constraints we can impose on a highly symmetric graph if we want to limit the automorphisms. It is with this approach in mind that we consider a natural edge-colouring.

Every Cayley graph comes with a natural edge-colouring that uses the elements of the connection set as the colours. It has long been known that for every connected Cayley digraph on a group $G$, the regular representation of $G$ provides the only automorphisms that preserve this colouring. However, in the case of an undirected Cayley graph Cay$(G,S)$ and $s \in S$, we must identify the colours $s$ and $s^{-1}$ since they apply to the same undirected edge. One effect of this is that some group automorphisms (those that map each $s \in S$ into ${s,s^{-1}}$) also preserve this colouring. Together with the regular representation of $G$, these are known as affine maps on the graph. In some cases there are additional graph automorphisms that are not affine maps.

We say that a Cayley graph is CCA, or has the CCA-property, if all of its colour-preserving automorphisms are affine. Similarly, we say that a group is CCA, or has the CCA-property, if every connected Cayley graph on that group is CCA. I will describe many of the known results on CCA groups and graphs, including joint work with Ted Dobson, Brandon Fuller, Ademir Hujdurovi\v{c}, Klavdija Kutnar, Luke Morgan, Dave Witte Morris, and Gabriel Verret.