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!

  • 2
    $\begingroup$ The fact that color-preserving automorphisms are elements of $G$ does not depend on having a finite number of generators; the proof is the same. As for non-color preserving examples, take your $G$ to be the free group on $2$ generators. The group of automorphisms of the Cayley graph has the cardinality of continuum. $\endgroup$ – Moishe Kohan Apr 30 '17 at 12:48
  • $\begingroup$ I'm actually more interested in the finitely generated or even finite case, that's why I added that on the question. Any example where the group is finite? $\endgroup$ – David Méndez Apr 30 '17 at 16:38

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:



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.