5 - Graphical Regular Representations and Pseudosimilarity

Summary

We have seen that the full automorphism group of a Cayley graph Cay(Γ, S) can be larger than Γ. If it happens that Aut(Cay(Γ, S)) is in fact equal to Γ, then, by Theorem 3.5, the automorphism group of Cay(Γ, S) acts regularly on V(Cay(Γ, S)). Conversely, if G is a graph whose automorphism group acts regularly on V(G), then G is a Cayley graph. (This follows from the second part of Theorem 3.5 and also from Sabidussi's Theorem because the stabiliser H in that theorem is trivial.)

A graph G whose automorphism group Γ = Aut(G) acts regularly on V(G) is called a graphical regular representation (GRR) of the group Γ. Therefore G is a GRR of its automorphism group Γ if it is vertex-transitive and the stabiliser Γ_v of any vertex is just the identity.

Note that in this case, by the Orbit-Stabiliser Theorem, |V(G)| = |Γ|. Also, given any two vertices u, v in G, there is one and only one automorphism α such that α(u) = v. Also, G − u has a trivial automorphism group for any vertex u.

Elementary results

Let us first consider the question of what conditions a graph must satisfy in order to be a GRR of its automorphism group. For convenience we shall state in the next theorem the main comments that we made in the introduction to this chapter, noting again that its proof follows from Theorem 3.5 or Sabidussi's Theorem.

Theorem 5.1Let G be a GRR of its automorphism group Γ. Then G is isomorphic to a Cayley graph Cay(Γ, S) for some set S that generates the group Γ.

Not any Cayley graph is, however, a GRR.

Lemma 5.2Let G = Cay(Γ, S) and let ϕ be an automorphism of Γ such that ϕ(S) = S. Then ϕ, as a permutation of V(G) = Γ, is an automorphism of G fixing the vertex 1.

Therefore, if ϕ is nontrivial, then G is not a GRR.

Proof Since ϕ is a group automorphism, ϕ(1) = 1. Also, ϕ is a graph automorphism Because

These results therefore imply that, for G to be a GRR, it (i) must be isomorphic to a Cayley graph Cay(Γ, S) and (ii) no nontrivial automorphism of Γ can fix the set S.