The Largest Laplace Eigenvalue

Let G be a simple and connected graph with n vertices and H be the line graph of G. Denote D and A be the diagonal matrix of vertex degrees and the adjacency matrix of G, while DH and B be the diagonal matrix of vertex degrees and the adjacency matrix of H, respectively. Let U=diag(dudv:uv∈E(G)) be a diagonal matrix. Then the matrix L=D-A and K=D+A is called the Laplacian matrix and the Qusi-Laplacian matrix of G, separately. The Laplacian eigenvalues of a graph are important in the graph theory, because they have a close relation to numerous graph invariants. In many applications, good upper bounds forλ1(G), the largest Laplacian eigenvalue of a graph G, are needed. In this paper, the following results are obtained:1.The main upper bounds forλ1(G) are summarized and compared in detail.2.Several new and sharp upper bounds forλ1(G) in terms of the vertex degree and the average 2-degree are obtained by applying nonnegative matrix theory to the similar matrix D^-1/2KD^1/2,D_H^-1/2BD_H^1/2 and U^-1/2BU^1/2, respectively. Moreover we determine all extremal graphs which achieve these upper bounds.And then some examples to illustrate that our results are better than the earlier and recent ones in some sense.3.An other type of upper bound forλ1(G) in terms of the degree sequence and the edge number of G are obtained by utilizing the inequality techniques and the relation of the matrix B with its eigenvalues, and we also determine the extremal graphs.4.In chapter three, some upper bounds for the Laplacian spectral radius of a graph with cut vertices or cut edges are given by separating the Laplacian matrix into two matrices and using famous Weyl theorem. These upper bounds are presented by the Laplacian spectral radius of the subgraphs of G which with large n. Furthermore, some examples show that these upper bounds are good in some cases.