Study On The Spectra Of Highly Symmetric Graphs And Related Problems

Algebraic graph theory is a subject to investigate the combinatorial properties of graphs by studying their algebraic properties using the knowledge of linear alge-bra,group theory,combinatorial design and so on.It is one of the most important branches in graph theory.As an important topic in Algebraic graph theory,Spectral graph theory focuses on the algebraic parameters,such as characteristic polynomi-als,eigenvalues and eigenspaces,of matrices associated with graphs,and investi-gates the relations between such parameters and the structure of graphs.Highly symmetric graphs mean the graphs with high symmetry,and they are such graphs with large automorphism group from the algebraic point of view.They always pos-sess good algebraic and combinatorial properties,and are the bridges connecting Graph theory,Combinatorial design and Algebraic theory.Therefore,highly sym-metric graphs play an important role in Spectral graph theory.There are abundant contents in such graphs.On the one hand,graphs with few distinct eigenvalues al-ways possess high symmetry.On the other hand,Cayley graphs are classical highly symmetric graphs.Accordingly,in this thesis,one the one hand,we characterize several classes of graphs with few distinct eigenvalues.On the other hand,we inves-tigate integral Cayley graphs and strongly regular Cayley graphs.Besides,we also study the spectra of a special class of anti-symmetric graphs(the so called threshold graphs)and a special class of high symmetric graphs(B(n,k)),respectivelyThere are four chapters in this thesis,which are organized as belowIn Chapter 1,we first introduce the background of Spectral graph theory;we next 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 thesisIn Chapter 2,we characterize several classes of graphs with few distinct eigen-values.In detail,we respectively characterize the graphs whose smallest distance eigenvalue has multiplicity n—3,the graphs whose smallest distance signless Laplacian eigenvalue has multiplicity n—2,the graphs whose distance Laplacian spectral radius has multiplicity n—3,and the graphs with exactly two distance eigenvalues(counting multiplicity)distinct from—1 and—3.The graph in the first or the fourth class has at most four distinct distance eigenvalues.The graph in the second class has at most three distinct distance signless Laplacian eigenvalues.The graph in the third class has at most four distinct distance Laplacian eigenvalues.In Chapter 3,we respectively study the distance spectra of threshold graphs and the graphs B(n,k),which are subgraphs of the hypercubes induced by the succes-sive layers.The threshold graphs always have weak symmetry,and such graphs are called anti-symmetric graphs.Anti-symmetric graphs always have many distinct distance eigenvalues.We investigate the spectral properties of threshold graphs and completely determine threshold graphs whose distance eigenvalues are all distinct.As an induced subgraph of the hypercubes,the graphs B(n?k)also possess high symmetry.We completely determine the distance spectrum of B(n,}k),and it has exactly four distinct distance eigenvalues.In Chapter 4,we study integral Cayley graphs and strongly regular Cayley graphs.On the one hand,we give some sufficient and necessary conditions for Cayley graphs over the dihedral group D,to be integral,and completely determine the integral Cayley graphs over Dp for prime p.On the other hand,we investigate strongly regular Cayley graphs over the elementary abelian 2-group Zg.We give a criterion for a vertex transitive graph to be strongly regular,and find several infinity classes of non-trivial strongly regular Cayley graphs over 22n'.