On the sum of Laplacian eigenvalues of graphs

被引：45

作者：

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
Brouwer, Andries E.
Haemers, Willem H.
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 429 (8-9) : 2131 - 2135
[3] Shifted simplicial complexes are Laplacian integral
Duval, AM
Reiner, V
[J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2002, 354 (11) : 4313 - 4344
[4] ON A THEOREM OF WEYL CONCERNING EIGENVALUES OF LINEAR TRANSFORMATIONS .1.
FAN, K
[J]. 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
Fulton, W
[J]. 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.
GRONE, R
MERRIS, R
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (02) : 221 - 229
[8] A note on Laplacian graph eigenvalues
Merris, R
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 1998, 285 (1-3) : 33 - 35
[9] Majorization bound for the eigenvalues of some graph laplacians
Stephen, Tamon
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (02) : 303 - 312
[10] On Laplacian eigenvalues of a graph
Zhou, B
[J]. ZEITSCHRIFT FUR NATURFORSCHUNG SECTION A-A JOURNAL OF PHYSICAL SCIENCES, 2004, 59 (03): : 181 - 184

← 1 →