I feel like for this question it is just a matter of showing the mapping in both directions, from the group to the graph and the graph to the group.

So for the mapping from the group to the graph, I mapped the each group action in G to some path that a vertex will travel. The path will be composed of the edges corresponding to the generators of the group action. I then chose some arbitrary vertex and showed that mapping it in such a way is an automorphism as the ends would be the same. In these automorphisms, every vertex follows the same type of path (generator/edge sequence) to reach it's mapped vertex.

Now, for the other direction I am a little stuck. I initially tried to prove by contradiction: Suppose there exists an automorphism that does not map according to a group action. This would mean the generator/edge sequence would be different for each vertex. I then noted that there must exist one edge e such that it's end vertices will follow different generator/edge sequences to reach it's mapped destination. However, I realized that it's possible for them to still be neighbors after the mapping. I hope I haven't overlooked anything or interpreted graph automorphisms wrong!

Thanks for your help!

  • $\begingroup$ What do you mean by "labelled Cayley graph". $\endgroup$ – Chris Godsil Feb 10 '13 at 0:07
  • $\begingroup$ I think just the associated cayley graph that has the group elements labelled on the vertices. I'm not too sure though, I was just dealing with it that way $\endgroup$ – Azhuang Feb 10 '13 at 0:40
  • $\begingroup$ Well, the complete graph $K_n$ is a Cayley graph for any group of order $n$, and its automorphism group is the symmetric group $\mathrm{Sym}(n)$. $\endgroup$ – Chris Godsil Feb 10 '13 at 0:43
  • $\begingroup$ Ahh yeah, maybe it has something to do with the generators chosen - I'll have to get more details. Thanks! $\endgroup$ – Azhuang Feb 10 '13 at 2:15
  • $\begingroup$ Is there any restriction on Cayley graphs that would make the question claim true? $\endgroup$ – Azhuang Feb 10 '13 at 4:20

The Cayley graph $\Gamma = \Gamma(G,X)$ of a group $G$ is defined with respect to a generating set $X$ of $G$. It has the elements of $G$ as vertices and, for each $g \in G$ and $x \in X \cup X^{-1}$, a directed edge labelled $x$ from $g$ to $gx$. An edge labelled $x$ is often identified with the edge labelled $x^{-1}$ in the other direction. Since $X$ generates $G$, $\Gamma$ is connected.

For each $h \in G$, we can define a map $T_h$ (translation by $h$) $\Gamma \to \Gamma$ by $T_h:g \mapsto hg$ for $g \in G$. Then it is easy to see that $T_h \in {\rm Aut}(\Gamma)$ and $h \mapsto T_h$ is an injective homomorphism $G \to {\rm Aut}(\Gamma)$, so we can identify $G$ with a subgroup of ${\rm Aut}(\Gamma)$. This subgroup acts regularly (i.e. transitively and with trivial stabilizers) on $\Gamma$, so to prove that it is equal to ${\rm Aut}(\Gamma)$, it is sufficient to prove that the stabilizer in ${\rm Aut}(\Gamma)$ of a vertex in $\Gamma$ is trivial.

The directed edges from a vertex $g$ in $\Gamma$ all have different labels (they do not necessarily have distinct targets, but that doesn't matter), and so an automorphism of the labelled graph that fixes $g$ must fix all vertices with source $g$ and hence, since $\Gamma$ is connected, it must fix all vertices and hence is trivial.

If you just consider the Cayley graph as an unlabelled graph, then it could have a larger automorphism group.

  • $\begingroup$ Ahh thanks! I think I neglected to realize that the labeled cayley graph has fixed positions for the edges $\endgroup$ – Azhuang Feb 10 '13 at 17:12

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.