Relations Between Multiplicity Of Eigenvalues And Several Structural Parameters Of Graphs

The multiplicity of an eigenvalue in a graph is closely related to its structural parameters,such as girth,matching number,cyclomatic number,order,and number of pendant vertices.An important research direction of spectral graph theory is how to utilize the algebraic properties of graphs to reflect structural features.The multiplicity of eigenvalues,which has been extensively studied in algebraic properties,has been proved to be closely related to the structural characteristics of graphs.Among them,nullity(multiplicity of eigenvalue 0)is often used for analyzing the stability of chemistry molecules,and multiplicity of eigenvalues-1 is also a research object emerging in recent years.One of the twelve research directions in algebraic graph theory proposed by Cvetkovic is to classify graphs using the spectra of corresponding matrices.As the adjacency matrix has been studied maturely,the research on its multiplicity of eigenvalues and structure parameters is still insufficient.This thesis focuses on the quantitative relations between the eigenvalues multiplicity and structure parameters of the adjacency matrix of graphs,and classifies graphs that attain a certain bound.In this graduation thesis,we mainly study the multiplicity of eigenvalues of the adjacency matrix of graphs with fixed parameters,give the quantitative relationship between the multiplicity of eigenvalues and the structural parameters,and characterize extremal graphs that reach upper or lower bounds.The specific research work is as follows:In Chapter 1,we introduced the research background of spectral theory and the related research progress of eigenvalue multiplicity,providing some basic concepts and explanations of related notations.In Chapter 2,based on the given upper bound of nullity of graphs with fixed girth,extremal graphs that reach two upper bounds were completely characterized,further improving Rowlinson’s([64])research on the girth of graphs.In Chapter 3,Wang[46]used matching number and cyclomatic number to give the upper and lower bounds of nullity of graphs,and characterized the correlation extremal graphs.This graduation thesis further investigates the relations between nullity and the number of odd cycles and even cycles in the case of a dense graph(with a fixed number of cycles,the cyclomatic number is large enough),and characterize the correlation extremal graph.In chapter 4,the problem of nullity and singularity in cycle-separated graphs was studied.It was proved that when the graph G is a bipartite graph,0≤η(G)≤c(G)+1,and extremal graphs that reach upper and lower bounds were characterized.Furthermore,the singularity of graph G is studied when all cycles are odd.In Chapter 5,using the relevant theories of star sets and star complements,the upper bound of m(T,μ)with μ≠1 given by Rowlinson was optimized,and the extremal graphs that attained the upper bound are characterized.In Chapter 6,we studied problem of the upper bound of the multiplicity of eigenvalue-1 of graphs with respect to the cyclomatic number and the number of pendant vertices.We characterized extremal graphs that reached the upper bound and partially solved the open problem proposed by Wang[47].In Chapter 7,we summarize the main results of this thesis and introduce some relevant contents for subsequent research.