The Turán number, denoted by ex (n, H), is the maximum number of edges of a graph on n vertices containing no graph H as a subgraph. Denote by kCℓ the union of k vertex-disjoint copies of Cℓ. In this paper, we present new results for the Turán numbers of vertex-disjoint cycles. Our first results deal with the Turán number of vertex-disjoint triangles ex (n, kC3). We determine the Turán number ex(n, kC3) for <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10114_2025_3272_Article_IEq1.gif" Format="GIF" Height="25" Rendition="HTML" Resolution="72" Type="Linedraw" Width="71" /> </InlineMediaObject> <EquationSource Format="TEX">$n \geq {k^{2}+5k \over 2}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>n</mi> <mo>≥</mo> <mrow> <mfrac> <mrow> <msup> <mi>k</mi> <mrow> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mn>5</mn> <mi>k</mi> </mrow> <mn>2</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation> when k ≤ 4, and n ≥ k2 + 2 when k ≥ 4. Moreover, we give lower and upper bounds for ex (n, kC3) with <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10114_2025_3272_Article_IEq2.gif" Format="GIF" Height="25" Rendition="HTML" Resolution="72" Type="Linedraw" Width="111" /> </InlineMediaObject> <EquationSource Format="TEX">$3k \leq n \leq {k^{2}+5k \over 2}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mn>3</mn> <mi>k</mi> <mo>≤</mo> <mi>n</mi> <mo>≤</mo> <mrow> <mfrac> <mrow> <msup> <mi>k</mi> <mrow> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mn>5</mn> <mi>k</mi> </mrow> <mn>2</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation> when k ≤ 4, and 3k ≤ n ≤ k2 + 2 when k ≥ 4. Next, we give a lower bound for the Turán number of vertex-disjoint pentagons ex (n, kC5). Finally, we determine the Turán number ex (n, kC5) for n = 5k, and propose two conjectures for ex (n, kC5) for the other values of n.

Turán Numbers for Vertex-disjoint Triangles and Pentagons

期刊论文
发表日期：

2025年4月15日

查看全文

Fangfang Wu,
Hajo Broersma,
Shenggui Zhang,
Binlong Li

摘要

The Turán number, denoted by ex (n, H), is the maximum number of edges of a graph on n vertices containing no graph H as a subgraph. Denote by kC_ℓ the union of k vertex-disjoint copies of C_ℓ. In this paper, we present new results for the Turán numbers of vertex-disjoint cycles. Our first results deal with the Turán number of vertex-disjoint triangles ex (n, kC₃). We determine the Turán number ex(n, kC₃) for $n \geq {k^{2}+5k \over 2}$ $n \geq \frac{k^{2} + 5 k}{2}$ when k ≤ 4, and n ≥ k² + 2 when k ≥ 4. Moreover, we give lower and upper bounds for ex (n, kC₃) with $3k \leq n \leq {k^{2}+5k \over 2}$ $3 k \leq n \leq \frac{k^{2} + 5 k}{2}$ when k ≤ 4, and 3k ≤ n ≤ k² + 2 when k ≥ 4. Next, we give a lower bound for the Turán number of vertex-disjoint pentagons ex (n, kC₅). Finally, we determine the Turán number ex (n, kC₅) for n = 5k, and propose two conjectures for ex (n, kC₅) for the other values of n.