Study On The Spectra And Isomorphisms Of Cayley Graphs And Some Related Problems

Algebraic graph theory is one of the most important research fields in graph theory,which mainly use algebraic methods to solve problems related to graphs.There are three main branches in algebraic graph theory,i.e.,graph and linear algebra,graph and group theory,and graph invariants.The first branch mainly study spectra of graphs,the second mainly study graphs with some specific symmetry,and the third mainly study algebraic properties of invariants of graphs.Cayley graphs,as a class of graphs with relatively good symmetry,are important research objects in the first two branches of algebraic graph theory.Particularly,to investigate the adjacency spectral gap,isomorphism classification and automorphism groups for Cayley graphs has important theoretical significance and application value.Graphs with few eigenvalues are always highly symmetric,and the problem of characterizing such graphs has received a lot of attention over the past twenty years.For these reasons,this thesis focuses on studying those problems related to the adjacency spectral gap,isomorphism classification and automorphism groups of Cayley graphs and the problem of characterizing those graphs with few eigenvalues.There are five chapters in this thesis,which are organized as below.In Chapter 1,we first introduce the background of algebraic graph theory;second we give some basic notions and symbols;and then we summarize the research progress of related problems involved in this thesis;finally,we list the main results of the thesis.In Chapter 2,we study the adjacency spectral gap of Cayley graphs.First of all,we prove that,for a Cayley graph G,those eigenvalues not belonging to the divisor matrix with respect to some specific equitable partition of G could be bounded above by the sum of second largest eigenvalues of some subgraphs of G;secondly,for a connected(conjugated)normal Cayley graph G,we reduce the problem of proving that the second largest eigenvalue of G equals to that of the divisor matrix with respect to some specific equitable partition of G to that of verifying the result for some small graphs;finally,we determine the adjacency spectral gap of a majority of connected(conjugated)normal Cayley graphs G = Cay(Sn,T)(and some subgraphs of these graphs)on S,satisfying maxτ∈T|supp(τ)| ≤ 4,and give a lower bound for the isoperimetric number of such graphs.In Chapter 3,we study the isomorphism classification and enumeration of Cayley graphs on dihedral group D2p(p is an odd prime).First of all,we determine all isomorphic classes of cubic Cayley graphs on D2p by means of spectral method(the obtained results coincide with the fact that D2p is a CI-group)and show that each cubic Cayley graph on D2p is Cay-DS;secondly,we obtain the number of isomorphic classes of cubic Cayley graphs on D2p by using Gauss’ celebrated law of quadratic reciprocity;finally,by using Polya enumeration theorem and the fact that D2p is a DCI-group,we determine the number of Cayley(di-)graphs on D2p up to isomorphism,and in particular,we enumerate Cayley digraphs on D2p of out-degree k for each k.In Chapter 4,we study the automorphism groups of some Cayley graphs on alternating group An and symmetric group Sn.First of all,we prove that the complete alternating group graph CAGn = Cay(An,S,)(here S is the set consisting of all 3-cycles in Sn,and n ≥ 4)is not a normal Cayley graph;secondly,by analyzing the local structure and considering the upper bound for the order of the automorphism group,we completely determine the automorphism group of CAGn,finally,we also determine the automorphism group of a class of cubic Cayley graphs on Sn.In Chapter 5,we study the problem of characterizing those graphs with few eigenvalues.First of all,we completely characterize connected regular graphs with exactly four distinct(adjacency)eigenvalues of which two are simple and one is-1(or 0),and show that all these graphs are determined by their adjacency spectra;secondly,we characterize all connected graphs with exactly three distinct normalized Laplacian eigenvalues of which one is 1,and determine all connected bipartite graphs with at least one pendant vertex having exactly four distinct normalized Laplacian eigenvalues;finally,we characterize all connected graphs with third largest distance eigenvalue not greater than-1 and second least distance eigenvalue not less than-2,and determine the connected graphs with at most three distance eigenvalues different from-1 and-2.