On a Lower Bound for the Laplacian Eigenvalues of a Graph

摘要

If mu(m) and d(m) denote, respectively, the m-th largest Laplacian eigenvalue and the m-th largest vertex degree of a graph, then mu(m) >= d(m) - 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 mu(m) = d(m) - m + 2. In particular we give a full classification of graphs with mu(m) = d(m) - m + 2 <= 1.