Tight lower bound for the spectral radius of connected graphs with given matching number

Abstract

Let ${\mathcal{G}}_{n,k}$ denote the family of all connected graphs of order $n$ with matching number $k$. Liu, Lou, and Trevisan~(Linear Algebra Appl., 2026) posed the following problem: Determine the spectrally minimal graphs in ${\mathcal{G}}_{n,k}$. In this paper we prove that for every graph $G\in {\mathcal{G}}_{n,k}$, $\rho (G)\ge \sqrt{\frac{n+2k-3}{k}},$ and we completely characterize the extremal graphs when $k\mid (n-3)$. As applications, we establish $\rho (G)+k\ge 3\sqrt[3]{n/4}$ for $k\ge 2$, settling the asymptotic order of $\rho +k$ as $\Theta (n^{1/3})$ -- strictly smaller than the $\Theta (\sqrt{n})$ order suggested by the disproved Aouchiche--Hansen conjecture.

arXiv comment11 pages, 3 figures