The Least Eigenvalue Of The Signless Laplacian Matrix Of Graphs

The spectral graph theory mainly researches the adjacency spec-trum, Laplace spectrum and signless Laplacian spectrum of graphs. In particular, it focuses on the properties of the extreme eigenvalues of graphs, such as the properties of the spectral radius or the least eigenvalue. It is the major goal of the spectral graph theory to char-acterize the structure properties of graphs by the spectral properties of graphs. In1985, Brualdi and Hoffman characterized the graph of which the adjacency spectral radius attains maximum among some class of graphs. This kind of problems are called the extremal graph problems.A lot of researchers investigate the extremal graph problems of the least eigenvalue since the least eigenvalue can characterize the structure properties of graphs very well. There are a lot of results about the extremal graph problems of the least eigenvalue of adjacency matrix, but there are few results about the extremal graph problems of the least eigenvalue of the signless Laplacian matrix. Comparing the least eigenvalue of the signless Laplacian matrix with the least eigenvalue of adjacency matrix, the least eigenvalue of the signless Laplacian matrix can characterize the structure properties of graphs more precisely. Therefore, the extremal graph problems of the least eigenvalue of the signless Laplacian matrix are investigated intensely now. The thesis mainly discusses the graphs minimizing or maximizing the least eigenvalue of the signless Laplacian matrix among certain class of graphs with given parameters, where the parameters that we discuss are the number of pendant vertices, girth, the number of cut vertices, the number of cut edges and chromatic number.The thesis is organized as follows. In Chapter1, we first intro-duce the background, and then discuss some concepts and notations used in this thesis, finally, we present the problem of the extremal graphs and its development, and the main results we obtained. In Chapter2. we first characterize the graph minimizing the least eigen-value of the signless Laplacian matrix among all unicyclic graphs of order n with given the number of pendant vertices and odd girth. Then we discuss the least eigenvalues of the signless Laplacian matrix among all connected non-bipartite graphs of order n with given the number of pendant vertices, and characterize the graph minimizing the least eigenvalue of the signless Laplacian matrix in this class of graphs. Finally, we characterize the graph minimizing the least eigen-value of the signless Laplacian matrix among all connected graphs of order n with three chromatic number. In Chapter3, we first discuss the least eigenvalues of the signless Laplacian matrix among all non-bipartite graphs of order n with given the number of pendant vertices, and characterize the graph maximizing the least eigenvalue of the sign-less Laplacian matrix in this class of graphs. Then we characterize the graph maximizing the least eigenvalue of the signless Laplacian ma-trix among all connected graphs of order n with just one cut vertex. Finally, we characterize the graph maximizing the least eigenvalue of the signless Laplacian matrix among all connected graphs of order n with just one cut edge.