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

2026/07/13 by Xinmin Hou, Li Tan
#math.CO

paper · pdf

Abstract

Let \mathscrG_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 \mathscrG_n,k. In this paper we prove that for every graph G ∈ \mathscrG_n,k, ρ(G) ≥ √((n + 2k - 3)/(k)), and we completely characterize the extremal graphs when k | (n-3). As applications, we establish ρ(G) + k ≥ 3√[3]n/4 for k ≥ 2, settling the asymptotic order of ρ+ k as Θ(n^1/3) -- strictly smaller than the Θ(√(n)) order suggested by the disproved Aouchiche--Hansen conjecture.

Related

• The spectral radius of graphs with fractional matching number
• The spectral radius of graphs with no K_2,t minor
• A spectral extremal problem on graphs with given size and matching number
• Maximum spectral radius of graphs with given connectivity and minimum degree
• Minimum spectral radius of graphs of fixed order and dissociation number and its connection to Turán problems