A set of cycles is called disjoint if no two of them have a common vertex. Let Sn,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 disjoint cycles, where k ≥ 2 and n ≥ 24k, we have e(G) ≤ (2k − 1)(n − k), with equality if and only if G ≅ Sn,2k−1. In this paper, we prove a spectral version of Erdös-Pósa Theorem. Let k ≥ 1 and <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$n \geq {{16(2k-1)} \over {\lambda^{2}}}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>n</mi> <mo>≥</mo> <mrow> <mfrac> <mrow> <mn>16</mn> <mo stretchy="false">(</mo> <mn>2</mn> <mi>k</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mrow> <msup> <mi>λ</mi> <mrow> <mn>2</mn> </mrow> </msup> </mrow> </mfrac> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\lambda = {{1} \over {120k^{2}}}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>λ</mi> <mo>=</mo> <mrow> <mfrac> <mrow> <mn>1</mn> </mrow> <mrow> <mn>120</mn> <msup> <mi>k</mi> <mrow> <mn>2</mn> </mrow> </msup> </mrow> </mfrac> </mrow> </math></EquationSource> </InlineEquation>. If G is a graph of order n which contains no k disjoint cycles, then ρ(G) ≤ ρ(Sn,2k−1), the equality holds if and only if G ≅ Sn,2k−1. From the perspective of counting subgraphs, our result implies that every graph G with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\rho(G) \geq \Theta(n^{3 \over 5})$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>ρ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mfrac> <mn>3</mn> <mn>5</mn> </mfrac> </mrow> </msup> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation> contains at least <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\Theta(n^{1 \over 5})$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mfrac> <mn>1</mn> <mn>5</mn> </mfrac> </mrow> </msup> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation> disjoint cycles. Finally, a related problem is proposed for further research.

A Spectral Erdös-Pósa Theorem

期刊论文
发表日期：

2025年5月29日

查看全文

Ming-qing Zhai,
Rui-fang Liu

摘要

A set of cycles is called disjoint 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 disjoint cycles, where k ≥ 2 and n ≥ 24k, we have e(G) ≤ (2k − 1)(n − k), with equality if and only if G ≅ S_n,2k−1. In this paper, we prove a spectral version of Erdös-Pósa Theorem. Let k ≥ 1 and $n \geq {{16(2k-1)} \over {\lambda^{2}}}$ $n \geq \frac{16 (2 k - 1)}{λ^{2}}$ with $\lambda = {{1} \over {120k^{2}}}$ $λ = \frac{1}{120 k^{2}}$ . If G is a graph of order n which contains no k disjoint cycles, then ρ(G) ≤ ρ(S_n,2k−1), the equality holds if and only if G ≅ S_n,2k−1. From the perspective of counting subgraphs, our result implies that every graph G with $\rho(G) \geq \Theta(n^{3 \over 5})$ $ρ (G) \geq Θ (n^{\frac{3}{5}})$ contains at least $\Theta(n^{1 \over 5})$ $Θ (n^{\frac{1}{5}})$ disjoint cycles. Finally, a related problem is proposed for further research.