On the sum of Laplacian eigenvalues of graphs

被引：46

作者：

Haemers, W. H. ^{[1
]}

Mohammadian, A. ^{[2
,3
]}

Tayfeh-Rezaie, B. ^{[3
]}

机构：

[1] Tilburg Univ, Dept Econometr & Operat Res, NL-5000 LE Tilburg, Netherlands

[2] Amirkabir Univ Technol, Fac Math & Comp Sci, Tehran, Iran

[3] IPM, Sch Math, Inst Res Fundamental Sci, Tehran, Iran

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2010年 / 432卷 / 09期

关键词：

Laplacian eigenvalues of a graph; Sum of eigenvalues; Largest eigenvalue;

D O I：

10.1016/j.laa.2009.03.038

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let k be a natural number and let G be a graph with at least k vertices. Brouwer conjectured that the sum of the k largest Laplacian eigen-values of G is at most e(G) + ((2) (k + 1)), 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. (C) 2009 Elsevier Inc. All rights reserved.

引用

页码：2214 / 2221

页数：8

共 10 条

[1]

BROUWER AE, 2008, SPECTRA GRAPHS UNPUB

[2] A lower bound for the Laplacian eigenvalues of a graph - Proof of a conjecture by Guo [J].

Brouwer, Andries E. ;

Haemers, Willem H. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 429 (8-9) :2131-2135

[3] Shifted simplicial complexes are Laplacian integral [J].

Duval, AM ;

Reiner, V .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2002, 354 (11) :4313-4344

[4] ON A THEOREM OF WEYL CONCERNING EIGENVALUES OF LINEAR TRANSFORMATIONS .1. [J].

FAN, K .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1949, 35 (11) :652-655

[5] Eigenvalues, invariant factors, highest weights, and Schubert calculus [J].

Fulton, W .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 2000, 37 (03) :209-249

[6]

Godsil C., 2001, Algebraic Graph Theory

[7] THE LAPLACIAN SPECTRUM OF A GRAPH .2. [J].

GRONE, R ;

MERRIS, R .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (02) :221-229

[8] A note on Laplacian graph eigenvalues [J].

Merris, R .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1998, 285 (1-3) :33-35

[9] Majorization bound for the eigenvalues of some graph laplacians [J].

Stephen, Tamon .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (02) :303-312

[10] On Laplacian eigenvalues of a graph [J].

Zhou, B .

ZEITSCHRIFT FUR NATURFORSCHUNG SECTION A-A JOURNAL OF PHYSICAL SCIENCES, 2004, 59 (03) :181-184

← 1 →