Published online by Cambridge University Press: 05 June 2016
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.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.