A group $G$ is said to admit a graphical regular representation (GRR) if there is a graph $\Gamma$ such that $Aut(\Gamma) \cong G$ and $G$ acts regularly on the vertices of $\Gamma$. Such a graph is called a GRR of the group $G$.
A graph $\Gamma$ is said to be a GRR if $Aut(\Gamma)$ acts regularly on the vertices of $X$. Sabidussi showed that a connected graph $\Gamma$ is isomorphic to a Cayley graph iff $Aut(\Gamma)$ contains a regular group. A Cayley graph $C(G,S)$ is said to be a GRR if its automorphism group is $G$ (which is the smallest possible full automorphism group for a Cayley graph $C(G,S)$). The question of determining, for a given $G,S$, whether $C(G,S)$ is a GRR, is a difficult and generally open problem.
The problem of which groups admit GRRs was resolved in the 1970s by the work of several authors and finally by (Godsil, 1978). It was proved that the only two infinite families of finite groups which do not admit GRRs are the abelian groups of exponent at least 3 and the generalized dicyclic groups. Each Cayley graph $C(G,S)$ on these two groups has a nontrivial automorphism so that $Aut(C(G,S))$ is strictly larger than $G$. Hence, these two families of groups do not admit GRRs. For all other groups, it is possible to construct at least one GRR for the group.
Recall that if $G$ is any group besides the two exceptions mentioned above, there is an $S$ such that $C(G,S)$ is a GRR. It was conjectured in (Babai and Godsil, "On the automorphism group of almost all Cayley graphs", Eur. J. Comb., 1982, Conjecture 2.1) that almost all Cayley graphs of such non-exceptional groups are GRRs.
Both the right regular representation $R(G)$ and the set $Aut(G,S)$ of automorphisms of $G$ that fixes $S$ setwise are automorphisms of the Cayley graph $C(G,S)$. $Aut(G,S)$ also fixes the identity vertex $e$. Observe that $Aut(C(G,S))$ equals $R(G) Aut(C(G,S))_e$, which contains $R(G)Aut(G,S)$. Thus, an equivalent condition for the Cayley graph $C(G,S)$ to be a GRR is that $Aut(C(G,S))_e =1$, and a necessary condition for $C(G,S)$ to be a GRR is that $Aut(G,S)=1$.
Since $Aut(G,S)$ might be easier to determine than $Aut(C(G,S))_e$, an open problem posed by (Godsil, "The automorphism groups of some cubic Cayley graphs", European Journal of Combinatorics, Eur. J. Comb., 25–32, 1983) is to determine conditions under which $C(G,S)$ is a GRR iff $Aut(G,S)=1$. Partial solutions to this problem include (Godsil, 1981, Combinatorica), (Li and Sim, Eur. J. Comb, 2000) and (Godsil, Eur. J. Comb, 1983).
If $G$ is abelian of exponent larger than 2 or generalized dicyclic, then $C(G,S)$ admits $G$ and a particular nontrivial map $i$ as automorphisms, and hence, $C(G,S)$ admits $G \rtimes \langle i \rangle$ (a group strictly larger than $G$) as a subgroup of automorphisms. Hence, $G$ does not admit a GRR. An open question was to determine whether almost all Cayley graphs of $G$ have the smallest possible automorphism group $G \rtimes \langle i \rangle$. This question was answered in the affirmatively recently by (Dobson, Spiga, and Verret, arXiv, 2014) for abelian groups and by (Morris, Spiga and Verret, 2015) for generalized dicyclic groups.
A Cayley graph $C(G,S)$ is said to be normal if $Aut(C(G,S))$ is exactly equal to $R(G) Aut(G,S)$. An open problem in the literature is to determine which Cayley graphs $C(G,S)$ are normal; see (Xu, "Automorphism groups and isomorphisms of Cayley digraphs", Discrete Math., 309–319, 1998). A conjecture is that almost all Cayley graphs are normal. More specifically, the conjecture is that if $G \ne Q_8 \times C_2^m$ is a group of order $n$, then the probability that a random Cayley graph of $G$ is normal approaches 1 as $n \rightarrow \infty$. A Cayley graph which is a GRR is also a normal Cayley graph, and so the conjecture that almost all Cayley graphs are normal is weaker than the conjecture that almost all Cayley graphs are GRRs. Non-normal Cayley graphs are rare, and to determine, for a given $G,S$, whether $C(G,S)$ is normal, is an open problem.
