A spectral Erdős-Pósa Theorem

Abstract

A set of cycles is called independent if no two of them have a common vertex. Let $S_{n,2k-1}$ be the complete split graph, which is the join of a clique of size $2k-1$ with an independent set of size $n-2k+1$. In 1962, Erdős and Pósa established the following edge-extremal result: for every graph $G$ of order $n$ which contains no $k$ independent cycles, where $k\ge 2$ and $n\ge 24k$, we have $e(G)\le (2k-1)(n-k),$ with equality if and only if $G\cong S_{n,2k-1}.$ In this paper, we prove a spectral version of Erdős-Pósa Theorem. Let $k\ge 1$ and $n\ge \frac{16(2k-1)}{{\lambda }^2}$ with $\lambda =\frac{1}{120k^2}$. If $G$ is a graph of order $n$ which contains no $k$ independent cycles, then $\rho (G)\le \rho (S_{n,2k-1}),$ the equality holds if and only if $G\cong S_{n,2k-1}.$ This presents a new example illustration for which edge-extremal problems have spectral analogues. Finally, a related problem is proposed for further research.

arXiv comment15 pages