Research On The Matrix Eigenvalues ??of Graphs

Some parts of the theory of graph spectra have been applied to many scientific ar-eas,such as mathematics,chemistry,physics and computer science.Researches on spectral graph theory are based on some properties of matrices of graphs.The methods translate properties of graphs into algebraic properties,by which we can deduce theorems about graphs.The priority of this thesis is adjacency matrix of a graph mentioned,as well as its signless Laplacian matrix,normalized Laplacian matrix and A?-matrix.The general contents are as the following.(a)We consider the spectral radius of adjacency matrix of a graph.By splitting matrix,we get the relation between the spectral radius of a graph and that of its induced subgraph with deleting a vertex.And then a new upper bound only related to the numbers of vertices and edges are deduced,which is better than a known upper bound which is also related to the numbers of vertices and edges of a graph.We also study effects upon the spectral radius of two operations on graph.We obtain upper bounds on the spectral radius of the coalescence of two graphs,which generalize some results by Passbani and Salemi.And we get effects upon the spectral radius by contracting an internal edge,which generalizes a result by Hoffman and Simth.(b)We investigate the multiplicity of zero as an eigenvalue of adjacency matrix.By method of star complement,we completely solve a conjecture proposed by Zhou,Wong and Sun.And the conjecture is about the nullity related to the number of vertices and the maximum degree of a connected graph.For all trees with n vertices and diameter d,we characterize all trees with its nullity satisfying ?=n-d or ?=n-d-1.Furthermore,all graphs with ?=n-d are also characterized.At the process of proof,we get the sufficiency and necessary condition that a caterpillar is minimal.(c)We investigate the second and the third least eigenvalues of adjacency matrix of a graph.Firstly,the structure relation between a connected graph and its connected sub-graphs is considered.Then we obtain the connected graphs with the first 4 largest second least eigenvalues by Cauchy inequality.Since Torgasev characterized canonical graphs with exactly two negative eigenvalues,we provide all graphs with the maximum third least eigen-value.(d)We investigate signless Laplacian matrix and normalized Laplacian matrix.We get information of the eigenvector corresponding the least signless Laplacian eigenvalue by considering the structure of a graph.In particular family of unicycle graphs,we characterize the graph minimizing the least signless Laplacian eigenvalue.Consequently,The graph with maximum signless Laplacian spread is determined.By computing tensor product of matrices,we investigate the effects of normalized Laplacian eigenvalues of a special class of graphs by adding edges.And then the effects of normalized Laplacian eigenvalues of a graph by adding edges into a cluster are obtained.We also prove that the normalized Laplacian energy will strictly increase when edges are added into a cluster.(e)We investigate A?-matrix of a graph.For a graph G with vertex v,edge e and in-duced subgraph H,we display the relations between the characteristic polynomial of Aa(G)and the corresponding polynomials of A?(G-v),A?(G-e)or Aa(G-H).These results generalize the corresponding results of A(G)by deleting a vertex v or an edge e and of L(G)by deleting a vertex v,an edge e or an induced subgraph H.We also show an upper bound of the kth A? eigenvalue of a tree,which in a sense generalizes results on adjacency matrix and Laplacian matrix by Shao and Guo respectively.