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 -