combinatorics

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

arXiv:2607.11061

summary

The paper establishes a tight lower bound for the spectral radius of connected graphs with a given matching number and characterizes the extremal graphs when the matching number divides n‑3, also deriving related bounds on the sum of spectral radius and matching number.

Abstract

Let $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 $G_{n, k}$ . In this paper we prove that for every graph $G \in G_{n, k}$ , $I ¨ (G) \geq \frac{n + 2 k - 3}{k},$ and we completely characterize the extremal graphs when $k ∣ (n - 3)$ . As applications, we establish $I ¨ (G) + k \geq 3 3 n /4$ for $k \geq 2$ , settling the asymptotic order of $I ¨ + k$ as $I^ (n^{1/3})$ -- strictly smaller than the $I^ (n)$ order suggested by the disproved Aouchiche--Hansen conjecture.

11 pages, 3 figures

Topics & keywords

#spectral graph theory #matching number #extremal graphs #lower bounds #connected graphsspectral radiusmatching numberconnected graphtight lower boundextremal characterization