# When is the automorphism group of the Cayley graph of $G$ just $G$?

Let $G$ be a finite group and $S$ a generating set of $G$. We can draw the Cayley graph $C(G,S)$ by putting each element of $G$ as a vertex, and drawing an edge between two elements $g$, $h\in G$ iff $g^{-1} h \in S$.

Choose $x\in G$. Note that the map $g \mapsto xg$ is a graph automorphism of $C(G,S)$. This allows us to embed $G \le \text{Aut}(C(G,S))$.

My question is: when is it in fact the case that $G = \text{Aut}(C(G,S))$? Is there a nice criterion to determine this?

• The set $S$ is requried to be minimal or arbitrary ? Jan 9, 2015 at 20:18
• Related: arxiv.org/pdf/1306.3747.pdf Jan 9, 2015 at 20:47
• @sameer Is something wrong with my answer? Jan 10, 2015 at 6:03

In general, there is no nice characterization of the connection sets $C$ such that the Cayley graph $\mathrm{Aut}(X(G,C)) \cong G$. (Such a graph is called a graphical regular representation for $G$, abbreviated (thankfully) to GRR.)

It is clearly necessary that the connection set generates the group.

If $G$ admits a non-identity automorphism that, for each element of $G$, either fixes it or maps it to its inverse, then the stabilizer of a vertex for any Cayley graph contains an element of order two. This rules out GRRs for abelian groups with exponent greater than two, and groups like the quaternion group (so-called generalized dicyclic groups).

If a group is not abelian with exponent greater than three, not generalized dicyclic, and has order at least 32 then it does have a GRR. (This is not trivial and rests on the work of a long list of people.)

If $G$ is nilpotent and not abelian, then almost all Cayley graphs for $G$ are GGRs (Babai and me). I proved (using some nontrivial group theory) that if $G$ is a $p$-group with no homomorphism on the the wreath product of $\mathbb{Z}_p$ by $\mathbb{Z}$, and $C$ is a connection set that is not fixed by any non-identity automorphism of $G$, then $X(G,C)$ is a GRR. So in this one case we do have a characterization of the connection sets that result in GRRs.

• Are you the David Godsil in the paper I linked? Jan 10, 2015 at 6:06
• @Modded Bear: Yes, but I am Chris (David is my middle name.) Jan 10, 2015 at 14:01

Observe that in Chris Godsil's answer all groups in questions are supposed to be finite.

For infinite groups, Watkins proved in 1974 that free products (with at most countably many factors) of groups always have a GRR, while we recently proved with Mikael de la Salle that an infinite finitely generated group which is neither abelian with exponent at least 3 nor generalized dicyclic has a GRR: https://arxiv.org/abs/1812.02199, https://arxiv.org/abs/2010.06020

First off: I don't know what I'm talking about. Pre-multiplying by an element of $G$ is a graph automorphism, hence the automorphism group of any Cayley graph contains a copy of $G$ as a subgroup. Apparently giving a generator $S$ such that the automorphism group is isomorphic to $G$ is called giving a Graphical Regular Representation, look at this article. Apparently finding a GRR of a group is called the GRR problem and is possible for all non-abelian subgroups of order coprime to $6$. Anyway, that article seems to have many other sources.

• Oh, now that I read your post you did say that we can embed $G$ into $Aut(C(G,S))$. So I think what I'm saying is good. Jan 9, 2015 at 20:43
• Apparently this is the paper which completes the characterization of groups that admit a GRR: books.google.com.mx/books/about/… Jan 9, 2015 at 20:45