Study On The Spectral Characterization Of Graphs With Few Distinct Eigenvalues

Algebraic graph theory is one of the most important research fields in graph theory,which mainly use algebraic methods to solve problems relat-ed 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 research core of the first branch is the graph spectral theory.The graph spectral theory mainly studies the combinatorial property of a graph through spectral characterization of some matrices associated with the graph such as adjacency matrix,Laplacian matrix,signless Laplacian matrix,normalized Laplacian matrix and distance matrix,etc.Graph spectral theory emerged in 1950s and 1960s,and get rapid development in the last 20 to 30 years.It is not only a cross field of graph theory,combinatorics and algebra,but also an important branch of algebraic graph theory.In 1957,The mathematical monograph”Spektren Endlicher Grafen”of L.Collatz and U.Sinogowitz is usually considered as the starting point of the study of spectral graph theory.In the past 50 years,The spectral graph theory has been developed into a research hot spot of algebraic graph theory and applied extensively to graph theory,physics,quantum chemistry,computer science,internet technology etc.The spectral characterization of graphs usually reflects the structural proper-ties of the graphs,especially the graphs with few distinct eigenvalues always have exceptional structures（such as highly symmetric）and nice combinatori-al properties.Currently,a lot of important advances have been made on the spectral characterization of graphs with 3 or 4 distinct eigenvalues.Howev-er,for given k<7,the problems of spectral characterization of graphs with exactly k distinct eigenvalues are far from resolved or have been incomplete-ly resolved.Based on this,our thesis focus on the spectral characterization of graphs with few distinct eigenvalues,including the spectral characteriza-tion of graphs with one of the Laplacian eigenvalue having large multiplicity,and the spectral characterization of walk-semiregular graphs with few distinct（adjacency）eigenvalues.There are three chapters altogether in the thesis.A brief organization is given in the following:In Chapter 1,we firstly introduce the background and some applications of graph spectra,then we give the notions,symbols and graphs involved in this work.Thirdly we briefly summarize the source,background of the problem.At last,we list our main results of the thesis.In Chapter 2,we study the graphs with one of the Laplacian eigenvalue having multiplicity m_L（μ）≥n-4.First,we characterize the graphs with one of the Laplacian eigenvalue having multiplicity n-3.Note that the graph of G_L（n,n-3）has three or four distinct Laplacian eigenvalues.We conclude that all graphs but G_n,rof G_L（n,n-3）are co-graphs,i.e.P₄-free graphs,which have their complements disconnected.Then,we determine the graphs of G_L（n,n-3）with three distinct Laplacian eigenvalues.Together with the results（the characterization of the graphs in G_L（n,n-3）with four distinct eigenvalues）of Mohammadian and Tayfeh-Rezaie,the full characterization of the graphs in G_L（n,n-3）is completed.Second,we focus on the graphs with the largest Laplacian eigenvalue having multiplicity n-4.By excluding all the forbidden subgraphs,we find that the graphs of G_L⁺（n,n-4）are co-graphs,which have their complements disconnected.Then we give a complete characterization of graphs in G_L⁺（n,n-4）（n≥5）.In addition,we also determine the graphs of G_L^-（n,n-4）（n≥8）,i.e.,the graphs with the second smallest Laplacian eigenvalues having multiplicity n-4.Furthermore,all the graphs we determined are DLS（determined by their Laplacian spectra）.In Chapter 3,we firstly give the definition of walk-semiregular.A（V₁,V₂）-semiregular graph G is called walk-semiregular if,for all l>0,the number of closed walks of length l from a vertex v∈V_i（i=1 or 2）is independent to the choice of v.Clearly,a walk-semiregular graph is always semiregular,but the converse is not true.We prove that the vertex partition of a semiregular graph is equitable if it is walk-semiregular and give a sufficient condition for a semiregular graph with 2-equitable partition to be walk-semiregular.Second,we mainly characterize the non-bipartite walk-semiregular graphs with four distinct eigenvalues.Let G^W（t,s）be the set of connected walk-semiregular graphs with t distinct eigenvalues in which exactly s eigenvalues are simple,and G^W（t,s;λ）the set of graphs belonging to G^W（t,s）withλas an eigenvalue.We first determine the graphs of G^W（3,s）with s≤2,and give a complete characterization of the graphs in G^W（4,3）.We give some properties of graphs of G^W（4,2）and mainly characterize the graphs belonging to G^W（4,2;0）.Fi-nally,we study the walk-semiregular bipartite graphs and mainly characterize the graphs with five distinct eigenvalues in terms of nullity,i.e.the nullity is largest,smallest or the second smallest multiplicity.Additionally,a neces-sary condition is given for the existence of the graph with the nullity in the remaining cases.