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_...
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 thi...
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 grap...
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\...
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...
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 que...
Le-Le Liu, Bo Ning· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
