TY - JOUR

T1 - On a Lower Bound for the Laplacian Eigenvalues of a Graph

AU - Greaves, Gary R.W.

AU - Munemasa, Akihiro

AU - Peng, Anni

N1 - Funding Information:
G.R.W.G. was at Tohoku University while this work took place and was supported by JSPS KAKENHI; Grant Number: 26.03903.
Publisher Copyright:
© 2017, Springer Japan KK.

PY - 2017/11/1

Y1 - 2017/11/1

N2 - If μm and dm denote, respectively, the m-th largest Laplacian eigenvalue and the m-th largest vertex degree of a graph, then μm⩾ dm- m+ 2. This inequality was conjectured by Guo (Linear Multilinear Algebra 55:93–102, 2007) and proved by Brouwer and Haemers (Linear Algebra Appl 429:2131–2135, 2008). Brouwer and Haemers gave several examples of graphs achieving equality, but a complete characterisation was not given. In this paper we consider the problem of characterising graphs satisfying μm= dm- m+ 2. In particular we give a full classification of graphs with μm= dm- m+ 2 ⩽ 1.

AB - If μm and dm denote, respectively, the m-th largest Laplacian eigenvalue and the m-th largest vertex degree of a graph, then μm⩾ dm- m+ 2. This inequality was conjectured by Guo (Linear Multilinear Algebra 55:93–102, 2007) and proved by Brouwer and Haemers (Linear Algebra Appl 429:2131–2135, 2008). Brouwer and Haemers gave several examples of graphs achieving equality, but a complete characterisation was not given. In this paper we consider the problem of characterising graphs satisfying μm= dm- m+ 2. In particular we give a full classification of graphs with μm= dm- m+ 2 ⩽ 1.

KW - Degree sequence

KW - Laplacian eigenvalues

UR - http://www.scopus.com/inward/record.url?scp=85026514883&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85026514883&partnerID=8YFLogxK

U2 - 10.1007/s00373-017-1835-y

DO - 10.1007/s00373-017-1835-y

M3 - Article

AN - SCOPUS:85026514883

SN - 0911-0119

VL - 33

SP - 1509

EP - 1519

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 6

ER -