Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
