Graph with sharply 1-transitive automorphism group

Question

What finite Graphs $G$ have the property that for all $v,w\in G$, there is exactly one automorphism $\phi$ of $G$ with $\phi(v)=w$? Of course, each of the three graphs with one or two vertices have this property, but are there any other examples?

Answer 1

If a graph has the property stated it is a graphical regular representation (abbreviated GRR) of its automorphism group. No characterization of these graphs is known, or at least none that is simpler than the definition. Note that any such graph is necessarily a Cayley graph for its automorphism group (as was first observed by Sabidussi.) The question has been studied is, given a group $\Gamma$, is there a Cayley graph $G$ for $\Gamma$ such that $\Gamma$ is the full automorphism group. To cut a long story very short, if $\Gamma$ has order at least 32 and is neither abelian with exponent greater than two nor generalized dicyclic, it does admit GRR. (Google for generalized dicyclic, the key property is that the "bad" groups admit a non-identity automorphism that fixes or inverts each element of $\Gamma$.)

In practice, if a group is big and not bad, most Cayley graphs for it are GRRs.

If $G$ is the Cayley graph for $\Gamma$ with connection set $C$ and there is a non-identity automorphism $\psi$ of $\Gamma$ that fixes $C$ as a set, then the automorphism group of $G$ is not regular. (This not hard to prove.) There are classes of groups for which the converse is true, e.g., $\mathbb{Z}_2^d$, and so these groups can be used to find actual examples.