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|+\binom{k+1}{2}$, 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.
Let $G=(V,E)$ be a finite simple graph with Laplacian eigenvalues $\lambda_1(L(G))\ge\cdots\ge\lambda_{|V|}(L(G))$, and define \[ \eps_k(G)= \sum_{j=1}^{\min\{k,|V|\}}\lambda_j(L(G))-|E|. \] Let $\nu(G)$ be the matching number of $G$, and let $n(G)$ be the number of non-isolated vertices of $G$. Lew proved that \(\eps_k(G)\le k\nu(G)+\lfloor k/2\rfloor\), and conjectured that the additive term can be removed in the non-endpoint range. We prove this conjecture: \[ \eps_k(G)\le k\nu(G) \qquad (1\le k\le n(G)-2). \] We also characterize all equality cases. Up to isolated vertices, equality holds precisely for stars, for \(K_1\vee(K_k\cup\overline{K_{n-k-1}})\) with \(k\) odd, and for \(K_n-E(K_{1,t})\) with \(n\) odd, \(k=n-2\), and \(1\le t\le n-2\). We also analyze the endpoint range \(k\ge n(G)-1\), where \(\eps_k(G)=|E|\), and determine the specific cases where the inequality \(\varepsilon_k(G)\le k\nu(G)\) fails or holds with equality.
Brouwer conjectured that the sum of the $k$ largest Laplacian eigenvalues of an $n$-vertex graph is less than or equal to the number of its edges plus $\binom{k+1}{2}$ for every $k\in \{1,2,\dots,n\}$, which has been confirmed by Kothari and Tudose (2026) recently. In this note, we characterize the equality case in this inequality. Our main result is that for every $n$-vertex graph $G=(V,E)$ and for every $k\in \{1,2,\dots,n-1\}$, the equality $\sum_{i=1}^k\mu_i(G)=|E(G)|+\binom{k+1}{2}$ holds if and only if $G$ is a threshold graph with clique number $k+1$, where $\mu_1(G)\geq \mu_2(G)\geq \cdots\geq \mu_{n}(G)$ are the Laplacian eigenvalues of $G$. This, together with the confirmed Brouwer's conjecture, would yield a complete solution to the full Brouwer's conjecture posed by Li and Guo (2022). Our proof relies on the projection method of Kothari and Tudose and shows directly that the equality case can occur only for threshold graphs.
For an integer $k\ge2$, let $\lambda_k(G)$ denote the $k$th largest adjacency eigenvalue of a graph $G$. For every graph $G$ on $n$ vertices and every $2 \leq k \leq n$, we prove \[ \lambda_k(G) \le \frac{(k-2)\sqrt{k+1}+2}{2k(k-1)}\,n-1. \] Our bound is tight for $k\in\{2,3,4,8,24\}$. We obtain it by reducing the graph-eigenvalue problem to an extremal problem for orthogonal projections and then applying the general upper bound on the absolute projection constant $\gamma(r)$ due to Der\k{e}gowska and Lewandowska. We also give an alternative proof of their bound by repairing the Gegenbauer-polynomial argument of K\"onig and Tomczak-Jaegermann. The resulting slack identity yields a strict improvement in every even dimension $r\ge4$ for which $r+2$ is not a perfect square.
Let $\alpha'(G)$ be the matching number of a graph $G$, and let its Randi\'c index be $R(G)=\sum_{uv\in E(G)}(d(u)d(v))^{-1/2}$. In 2006, Aouchiche, Hansen, and Zheng conjectured that the maximum of $R(G)-\alpha'(G)$ over all $n$-vertex graphs is attained by the complete bipartite graph whose smaller part has $\lfloor\frac{n+4}{7}\rfloor$ vertices; the conjecture has remained open since then. In this paper, we prove that every $n$-vertex K\"onig--Egerv\'ary graph, and in particular every bipartite graph, satisfies \[ R(G)\le\sqrt{\alpha'(G)\left(n-\alpha'(G)\right)}, \] and we characterize the graphs attaining equality as the bipartite graphs all of whose components are semiregular with a common degree ratio. The K\"onig--Egerv\'ary hypothesis cannot be dropped, but the Berge--Tutte formula reduces the general case to it, and in this way we determine the maximum of $R(G)-\alpha'(G)$ for every $n\ge4$, together with all extremal graphs. The conjecture is therefore false, and it fails for infinitely many orders: the optimal part size is governed by the proportion $\frac{2-\sqrt2}{4}$ rather than by $\frac17$. The two proportions give asymptotic slopes differing by less than $3.7\cdot10^{-5}$, which is why a search over graphs of small order does not distinguish them. The equality statement fails as well, since the extremal graphs are not only the complete bipartite ones.
Let $G$ be a graph of order $n$ with eigenvalues $\lambda_1(G) \geq \dots \geq \lambda_n(G)$, and let $s_+(G)=\sum_{\lambda_i(G)>0}\lambda_i(G)^2.$ Recently Liu, Tang, and Zhang proved the positive square-energy strengthening of Tur\'an's theorem \[\sqrt{s_+(G)}\leq \left(1-\frac1r\right)n.\] where $r=\omega(G)$ is the clique number of $G$. We characterize the families of graphs for which the above inequality is sharp. Precisely, we prove that, for $r\geq 2$, equality holds if and only if $r\mid n$ and $G$ is the complete regular $r$-partite graph $K_{n/r,\ldots,n/r}$.
Abhay Jayarajan, M. Kannan, Shivaramakrishna Pragada et al.· 0 citations
Let $G$ be a simple graph of maximum degree $d$, and let $\mu(G)$ denote the largest eigenvalue of its Laplacian matrix. For a fixed integer $k\geq 2$, Aharoni, Alon, and Berger (2016) asked whether every graph containing no induced copy of $K_{1,k}$ satisfies $\mu(G)\leq (2 - \frac{2}{k} + o(1)) d$. We answer this question by proving the stronger sharp bound \[ \mu(G)\leq \left(2-\frac{2}{k}\right)(d+1). \] The proof combines a sign decomposition of a Laplacian Rayleigh vector with a weighted local Caro-Wei type inequality for independent sets.
