Affordable Access

On the Sum of Laplacian Eigenvalues of Graphs

Authors

Abstract

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.

Statistics

Seen <100 times
0 Comments

More articles like this

On sum of powers of the Laplacian eigenvalues of g...

on Linear Algebra and its Applica... Dec 01, 2013

Upper bounds for the sum of Laplacian eigenvalues...

on Linear Algebra and its Applica... May 01, 2012

On sum of powers of the Laplacian eigenvalues of g...

on Linear Algebra and its Applica... Jan 01, 2008

On the sum of Laplacian eigenvalues of graphs

on Linear Algebra and its Applica... Jan 01, 2010
More articles like this..