Take $G$ a group and $S$ a generating set for it. The Cayley colour graph $\Gamma(G,S)$ is a directed and coloured graph defined as follows:
- Vertices in $\Gamma(G,S)$ are the elements of the group $G$.
- Each generator $s\in S$ is assigned a color $c_s$.
- For every $g\in G$ and $s\in S$, the vertices corresponding to the elements $g$ and $gs$ are joined by a directed edge $g\to gs$ labeled $c_s$.
We know that if the set of generators is finite, then the colour-preserving automorphisms of the graph are isomorphic to the group $G$, but lately I've been wondering how are automorphisms of the directed graph that are not color preserving (that is, bijective maps $\sigma\colon G\to G$ such that there is an edge $g\to h$ if and only if there is one $\sigma(g)\to\sigma(h)$, but which may receive different labels).
I've seen that it's not difficult to produce examples of Cayley graphs that admit automorphisms that are not color preserving. However, I observed in some simple examples that in general these automorphisms just permute the colours, so all edges with a given label $c_s$ are taken to edges with a label $c_{s'}$. My question is: does this happen in general (or in some restricted framework like finite groups) or are there examples of Cayley graphs that allow for (directed graph) automorphisms that don't permute the colours?
Thanks a lot!
If you take the complete graph on a group, as a Cayley graph, it typically will have many automorphisms that do not permute the color classes. (For example, the complete graph on the cyclic group of order 4 already has this property.)
If you want an example where the generating set is minimal, take say the wreath product $Z_2 \wr Z_n=\langle a\rangle \wr \langle b\rangle$ and take $S=\{b,ab\}$. The corresponding Cayley digraph will have a huge automorphism group, and many of the automorphisms won't preserve the colour classes.
See this paper for a closely related question:
https://arxiv.org/abs/1411.6732