Affordable Access

On the Sum of Laplacian Eigenvalues of Graphs



SumLap_1.dvi No. 2008–98 ON THE SUM OF LAPLACIAN EIGENVALUES OF GRAPHS By W.H. Haemers, A. Mohammadian, B. Tayfeh-Rezaie November 2008 ISSN 0924-7815 On the sum of Laplacian eigenvalues of graphs W.H. Haemers a, 1 A. Mohammadian b, c B. Tayfeh-Rezaie c aDepartment of Econometrics and Operations Research, Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands bFaculty of Mathematics and Computer Science, Amirkabir University of Technology, P.O. Box 15875-4413, Tehran, Iran cSchool of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran Abstract Let k be a natural number and let G be a graph with at least k vertices. A.E. Brouwer conjectured that the sum of the k largest Laplacian eigenvalues of G is at most e(G)+ ( k+1 2 ) , where e(G) is the number of edges of G. We prove this conjecture for k = 2. We also show that if G is a tree, then the sum of the k largest Laplacian eigenvalues of G is at most e(G) + 2k − 1. AMS Subject Classification: 05C50, 15A42. Keywords: Laplacian eigenvalues of a graph, Sum of eigenvalues, Largest eigenvalue. JEL code: C0. 1 Introduction Let G be a simple graph with the vertex set V (G) = {v1, . . . , vn}. The degree of a vertex v ∈ V (G), denoted by d(v), is the number of neighbors of v. The Laplacian matrix of G is the n × n matrix L(G) = [ℓij ] that records the vertex degrees d(v1), . . . , d(vn) on its diagonal and for any i 6= j, 1 6 i, j 6 n, ℓij = −1 if vi and vj are adjacent and ℓij = 0, otherwise. It is well-known that L(G) is positive semi-definite and so its eigenvalues are nonnegative real numbers. The eigenvalues of L(G) are called the Laplacian eigenvalues of G and are denoted by µ1(G) > µ2(G) > · · · > µn(G). Note that each row sum of L(G) is 0 and therefore, µn(G) = 0. In this paper, we investigate the sum Sk(G) = ∑k i=1 µi(G

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times