On The Nullity And Signless Laplacian Spectral Radius Of A Graph

ABSTRACT:In graph theory, in order to study the properties of graphs, various matrices that are naturally associated with a graph are introduced, such as adjacency matrix, incidence matrix, Laplacian matrix and signless Laplacian matrix and so on. The main problem of algebraic graph theory is to determine precisely how, or whether, properties of graphs are reflected in the algebraic properties of such matrices.In this thesis, we study the nullity and signless Laplacian spectral radius of a graph. The nullity of a graph is the multiplicity of the value zero in the spectrum of the adjacency matrix. It is closely related to the matching number of a graph. The simple graphs of order n with nullity n-2,n-3,n-4,n-5are characterized completely. Some results about special graph classes are obtained, such as tree, bipartite graph, unicyclic graph and bicyclic graph and so on. Some authors begin to focus on the nullity of a signed graph. All signed graphs with nullity n-2, n-3are characterized. All unicyclic signed graphs and bicyclic signed graphs with nullity n-4, n-5are also characterized. The spectrum (signless Laplacian spectrum) of a graph refers to all eigenvalues of the adjacency matrix (signless Laplacian matrix), the largest eigenvalue is called the spectral radius(signless Laplacian spectral radius) of the graph. There are a lot of results about adjacency spectrum, but few results about signless Laplacian spectrum. Comparing with adjacency spectrum, signless Laplacian spectrum has a close relation with the graph, so it attracts extensive attention of many researchers.In Chapter1, we introduce the basic concepts and notations. In Chapter2, we first give some properties and a survey of research on nullity of a (signed) graph, and then characterize the bicyclic signed graphs with nullity n-7. In Chapter3, we first summarize the existing results about upper bounds of the signless Laplacian spectral radius, and then obtain a upper bound on the signless Laplacian spectral radius of {Bk+l,K2,l+1}-free graphs. Moreover, we characterize the extremal graph which attains the sharp bound.