[Math] When is the automorphism group of the Cayley graph of $G$ just $G$

geometric-group-theorygraph theorygroup-theory

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?

Best Answer

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.

Related Question