The Equality Cases for the Grone-Merris-Bai Theorem

Abstract

The Grone--Merris inequality, conjectured by Grone and Merris~(1994) and first proved by Bai~(2011), states that for every graph $G$ of order $n$ and every $1\le k\le n$, ${\sum }_{i=1}^k\hat{I}{»}_i(G)\le {\sum }_{i=1}^k{d}_i^{\ast }(G)$, where $\hat{I}{»}_1\ge \cdots \ge \hat{I}{»}_n$ are the Laplacian eigenvalues and $d_1^{\ast }\ge \cdots \ge d_n^{\ast }$ is the conjugate degree sequence. In this paper we determine exactly when equality holds. Using the split-graph trace inequality developed by Kothari and Tudose~(2026) in their proof of Brouwer's Laplacian conjecture---which relies on Bai's theorem and also establishes the equivalence between the two conjectures---together with the recent characterization of the Brouwer equality cases by Cai, Chen, Yang and Zhang~(2027), we prove that equality holds in the Grone--Merris inequality if and only if the graph $G$ belongs to one of two explicitly described families. Both families are obtained from a threshold graph by a surgical operation at one terminal block: in the first family, edges are removed from the initial dominating block; in the second, edges are added inside the initial isolated block. Our analysis yields a complete combinatorial description of all pairs $(G,k)$ for which the Grone--Merris bound is tight.

16 pages