On a lower bound for the Laplacian eigenvalues of a graph

Gary R. W. Greaves; Akihiro Munemasa; Anni Peng

doi:10.1007/s00373-017-1835-y

paper

On a lower bound for the Laplacian eigenvalues of a graph

arXiv:1707.03221 · doi:10.1007/s00373-017-1835-y

Abstract

If $μ_{m}$ and $d_{m}$ denote, respectively, the $m$ -th largest Laplacian eigenvalue and the $m$ -th largest vertex degree of a graph, then $μ_{m} ⩾ d_{m} - m + 2$ . This inequality was conjectured by Guo in 2007 and proved by Brouwer and Haemers in 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} = d_{m} - m + 2$ . In particular we give a full classification of graphs with $μ_{m} = d_{m} - m + 2 ⩽ 1$ .

corrected typo