Research On The Eigenvalues And Related Problems Of Graphs

Spectral graph theory and random walks on graphs are two important branches in graph theory.Spectral graph theory mainly investigate the relationship among the topological properties and the eigenvalues of matrices of graphs,while random walks on graphs,as a significant application of approximation algorithm design,investigate the capabilities of random walks,such as hitting time and cover time.The research on spectral graph theory and random walks on graphs are both of important theoretical significance.In thesis,we apply the properties of the eigenvalues of graphs to investigate the(signless Laplacian)spectral radius of 2-domination critical graphs and the signless -Laplacian spectral radius of graphs with given parameter.Then,we study the degree reverse cover cost of graphs by using the properties of random walks on graphs.The specific content of this thesis is as follows:Firstly,the background and current development of spectral graph theory and related problems of graphs are summarized.Also,the related basic theories and concepts are presented.Next,we consider the problem about the upper bound of the spectral radius and the signless Laplacian spectral radius of 2-domination critical graphs.By applying the correlation among the characteristic polynomial of a graph and its complement and the number of walks in the graph and the correlation among the polynomial of a graph and its complement and the number of semi-walks in the graph,we obtained the characteristic polynomial and the polynomial of a 2-domination critical graph,respectively.Further,we obtain the upper bounds of the spectral radius and the signless Laplacian spectral radius of 2-domination critical graphs and the corresponding extremal graphs by utilizing analytical methods.Then,we consider the problem about the signless -Laplacian spectral radius of graphs with given parameters.By taking use of the properties of the-norm and the signless -Laplacian spectral radius,we gain two graph transformations which do not decrease the signless -Laplacian spectral radius of graphs.Further,these two graph transformations are applied to investigate the signless -Laplacian spectral radius of three certain class of graphs.Finally,the upper bounds of the signless -Laplacian spectral radius of graphs with given matching number,cut vertices,cut edges,diameter and unicyclic graphs with given degree sequence and the corresponding extremal graphs are obtained.Finally,we consider the problem about the upper and lower bounds of the weighted reverse cover cost of trees and unicyclic graphs.Primarily,we prove that there always exist a maximum matching of any tree or non-cycle unicyclic graph which does not have a perfect matching such that all unsaturated vertices with respect to this maximum matching are pendent vertices.Then by applying the techniques of graph transformations,we obtain the upper and lower bounds of the weighted reverse cover cost of trees with given order,pendent vertices,vertices of degree 2 and matching number,respectively.Based on the results of trees,we further obtain the upper and lower bounds of the weighted reverse cover cost of unicyclic graphs.Finally,the lower bounds of the weighted reverse cover cost of unicyclic graphs with perfect matching or given matching number are obtained,respectively.