The Least Eigenvalue And The Laplacian Spectral Radius Of Graphs

The theory of graph spectra is an active and important area in graph theory. There are extensive applications in the fields of quantum chemistry, statistical mechanics, computer science, communication network and infor-mation science. The theory of graph spectra can be considered as an attempt to discover the properties on structures of graphs and the relations between the spectra and the invariants (e.g. chromatic number, degree sequence, di-ameter, girth and connectivity) of graphs by means of the well-developed theory and technique of algebra, theories of graph and combinatorics in or-der to establish firmly essential relation between the algebraic properties and topological properties of graphs and networks.In the theory of graph spectra, there are various matrices that are nat-urally associated with a graph, such as the adjacency matrix, the incidence matrix, the distance matrix and the Laplacian matrix. One of the main problems of graph spectra theory is to determine precisely how, or whether, properties of graphs are reflected in the algebraic properties (especially eigen-values) of such matrices.Among the above mentioned matrices of graphs, the most important two are the adjacency matrix and the Laplacian matrix of graphs. Both the eigenvalues of the adjacency matrix and the Laplacian matrix are the invari-ants of graphs under isomorphism. Among the eigenvalues of the adjacency matrix, the most important two are the largest eigenvalue and the smallest eigenvalue, and called the spectral radius and the least eigenvalue, respec- tively. There are many results which form a perfect theoretical system in the literature concerning the spectral radius, but much less is known about the least eigenvalue. Among the eigenvalues of the Laplacian matrix, the most important two are the largest Laplacian eigenvalue (the Laplacian spectral radius) and the second smallest Laplacian eigenvalue (algebraic connectiv-ity). This thesis mainly investigates the least eigenvalue and the Laplacian spectral radius of graphs.This paper firstly introduces the research background and progress about the least eigenvalue and the Laplacian spectral radius of graphs, and then the thesis is separated four parts to introduce our main results about the above two topics in detail. The main results of this thesis are as follows.(1) In Chapter 2, we study the general graphs with fixed diameter. Let gn,d be the set of connected graphs on n vertices with diameter d. For any graph G (?) gn,d, by considering the least eigenvalue of its connected spanning bipartite subgraph, we obtain a lower bound of the least eigenvalue of graph G. Furthermore, as a corollary, an upper bound of Laplacian spectral radius of graph G is given.(2) In Chapter 3, we investigate the relations between the least eigenval-ues and the invariants of graphs. Let u(n, k) be the set of unicyclic graphs with n vertices and k pendant vertices. By using the technique of graft transformation of graphs and the characteristic polynomial, we determine the unique graph with minimal least eigenvalue among all graphs in u(n, k). Let B(n, k) be the set of bicyclic graphs with n vertices and k pendant ver-tices. By using tools and methods of spectral graph theory, the unique graph with minimal least eigenvalue among all graphs in B(n, k) is characterized. In the last section of this chapter, we study the invariant of graph-diameter. Let u(n, d) be the set of unicyclic graphs on n vertices with diameter d, we determine the unique graph with minimal least eigenvalue among all graphs in u(n,d).(3) In Chapter 4, we investigate the spectra of tricyclic graphs. Let gn be the set of tricyclic graphs of order n, we determine the unique graph with minimal least eigenvalue among all graphs in this class for each n≥52.(4) In Chapter 5, we study the Laplacian spectral radius of trees. Let Tn,d be the set of trees on n vertices with diameter d. For d (?) {1,2,3,4, n -4, n - 3, n - 2, n - 1}, trees with minimal Laplacian spectral radii in the set Tn,d are characterized.