Automorphism Groups Of Some Families Of Popular Cayley Graphs

To determine the automorphism groups of Cayley graphs is avery important and active problem in the field of algebraic graphtheory. Generally speaking, it is a very difcult problem. In recentdecades, although there are many good results on the automorphismgroups of Cayley graph, up to now, it is still no hope to solve com-pletely this problem.In this thesis, we study the automorphism groups of some fami-lies of popular Cayley graphs, including the derangement graphs, thetensor powers of even derangement graphs and the famous pancakegraphs, some important invariants, such as chromatic number, cliquenumber, independence number and spectrum, are also investigatedfor some of these families of graphs. One thing to be mentioned,we determine the automorphism groups of Cayley graphs by repeat-edly using the structure of their maximal-size independent sets, untilnow, this method has rarely been used to obtain the automorphismgroups of Cayley graphs. In this thesis we investigate the followingproblems.First for the derangement graph, we prove that its automor- phism group is (R(Sn) Inn(Sn)) Z2, where R(Sn) and Inn(Sn) arethe right regular representation and the inner automorphism groupof the symmetric group Snrespectively, and Z2is the cyclic groupof order2generated by the inverse map of Sn; By proving this re-sult, we obtain an upper bound on the order of the automorphismgroup of any Cayley graph of the symmetric group which satisfiescertain condition. Using the result on the automorphism group ofthe derangement graph, we completely determine its all edge-orbits.In addition, we study the spectrum of the derangement graph, byderiving a formula for all the eigenvalues corresponding to the2-partpartitions, we determine the exact value for the second largest eigen-value of the derangement graph; As an application of this result, wegive the upper and lower bounds for the Cheeger constant, Moreover,we also obtain an upper bound for the bipartite density and the exactvalue of the Shannon capacity.Then for the tensor powers of the even derangement graphs, wecharacterize their some properties, such as: connectivity, diameter,independent number, clique number and chromatic number, more-over, we show that all maximal-size independent sets of the tensorpowers of the even derangement graphs are the cosets of the stabi-lizer of a point, this generalizes one result of Ku and Wong[59]; Usingthe structure of the maximal-size independent sets, we prove thatthe automorphism group of the tensor power of q copies of the even derangement graphs is (R(Anq)(?)(Inn(Sn)(?)Sq))(?) Z2q, where R(Anq is the right regular representation of the direct product Anq of the alternative groups, Inn(Sn) is the inner automorphism group of the symmetric group Sn, Z2q is the direct product of the cyclic groups of order2, and Inn(Sn)(?)Sq denote the wreath product of Inn(Sn) and sq.Finally, about the pancake graph, by using the result on its effi-cient dominating sets, we intensively investigate the structure of the pancake graphs, and prove that the automorphism group of the pan-cake graph is isomorphic to the right regular representation of the symmetric group, i.e., the pancake graph is a graph regular represen-tation of the symmetric group. In addition, we also investigate the super-connectivity and hyper-connectivity of the pancake graphs.