Proofs of two conjectures on generalizations of Brouwer's Laplacian conjecture

Abstract

Let $G=(V,E)$ be a simple graph of order $n$ and let ${\lambda }_1(G)\ge \cdots \ge {\lambda }_n(G)$ be the eigenvalues of its Laplacian matrix. Brouwer conjectured that for every $1\le k\le n$, ${\sum }_{i=1}^k{\lambda }_i(G)\le |E|+\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)$, which was recently confirmed by Kothari and Tudose. Before Brouwer's conjecture was proved, Lew (JCT-B, 2026) established a weaker form of Brouwer's Laplacian eigenvalue inequality and proposed two conjectures for upper bounds on the sum of the $k$ largest Laplacian eigenvalues, one in terms of the matching number and the other in terms of the vertex-cover number. Using Brouwer's Laplacian inequality, we prove both conjectures.

11 pages