281 Graphs1020300010100Fig. 1.21. An embedding of the Shrikhande graph on the torus1.3.18 CAYLEY GRAPHLet T be a group, and let S be a set of elements of I not including the identityelement. Suppose, furthermore, that the inverse of every element of S also belongstoS.The Cayley graphofwithrespect toSisthegraph CG(,S) with vertexset r in whichverticesandyareadjacentif and onlyif ry-iES.(Notethat, because S is closed under taking inverses, if ry-1 e s, then yr-1 e s.)a) Show that the n-cube is a Cayley graphb) Let G be a Cayley graph CG(r,S) and let a be an element ofr.i) Show that the mapping Q defined by the rule that ar(y) = ry is anautomorphism of G.i) Deduce that every Cayley graph is vertex-transitive.c)Byconsidering the Petersen graph, show that not every vertex-transitive graphs a Cayley graph.1.3.19 CIRCULANTA circulant is a Cayley graphCG(Zn,S), where Z, is the additivegroupofintegersmodulo n. Let p be a prime, and let i and j be two nonzero elements of Zpa) Show that CG(Zp, (i, -il) = CG(Zp (j, -j),b) Determine when CG(Z, (1, -1,i, -ij) = CG(Zp, [1,-1,;j, -j).1.3.20 PALEY GRAPHLet q be a prime power, q= 1 (mod 4). The Paley graph PGg is the graph whosevertex set is the set of elements ofthefield GF(),two vertices being adjacentiftheir differenI nonzero square in GF(a)a) Draw PGs, PGg, and PG13b) Show that these three graphs are self-complementary.c) Let abe a nonsquare in GF(Q).By considering the mapping :GF(@)GF(α) defined by d(r) := ar, show that PGg is self-complementary for all q.28 1 Graphs 00 00 00 00 01 01 02 02 03 03 10 10 20 20 30 30 Fig. 1.21. An embedding of the Shrikhande graph on the torus 1.3.18 Cayley Graph Let Γ be a group, and let S be a set of elements of Γ not including the identity element. Suppose, furthermore, that the inverse of every element of S also belongs to S. The Cayley graph of Γ with respect to S is the graph CG(Γ,S) with vertex set Γ in which two vertices x and y are adjacent if and only if xy−1 ∈ S. (Note that, because S is closed under taking inverses, if xy−1 ∈ S, then yx−1 ∈ S.) a) Show that the n-cube is a Cayley graph. b) Let G be a Cayley graph CG(Γ,S) and let x be an element of Γ. i) Show that the mapping αx defined by the rule that αx(y) := xy is an automorphism of G. ii) Deduce that every Cayley graph is vertex-transitive. c) By considering the Petersen graph, show that not every vertex-transitive graph is a Cayley graph. 1.3.19 Circulant A circulant is a Cayley graph CG(Zn,S), where Zn is the additive group of integers modulo n. Let p be a prime, and let i and j be two nonzero elements of Zp. a) Show that CG(Zp, {i, −i}) ∼= CG(Zp, {j, −j}). b) Determine when CG(Zp, {1, −1,i, −i}) ∼= CG(Zp, {1, −1,j, −j}). 1.3.20 Paley Graph Let q be a prime power, q ≡ 1 (mod 4). The Paley graph PGq is the graph whose vertex set is the set of elements of the field GF(q), two vertices being adjacent if their difference is a nonzero square in GF(q). a) Draw PG5, PG9, and PG13. b) Show that these three graphs are self-complementary. c) Let a be a nonsquare in GF(q). By considering the mapping θ : GF(q) → GF(q) defined by θ(x) := ax, show that PGq is self-complementary for all q