The Turán number of k₁P_2l∪ k₂S_2l-1

2022/10/18 by Tao Fang, Xiying Yuan, Fang, Tao +1
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2210.09707

Abstract

The Turán number of a graph H, denoted by ex(n, H), is the maximum number of edges in any graph on n vertices containing no H as a subgraph. Let P_k denote the path on k vertices, S_k denote the star on k+1 vertices and k₁P_2l∪ k₂S_2l-1 denote the path-star forest with disjoint union of k₁ copies of P_2ls and k₂ copies of S_2l-1s. In 2019, Lan et al. determined the Turán numbers of kS_l and k₁P₄∪ k₂S₃. In 2022, Zhang et al. determined the Turán numbers of k₁P₆∪ k₂S₅ and raised a conjecture of the Turán numbers of k₁P_2l∪ k₂S_2l-1, where k₁\geqslant 1 and l\geqslant 2. In this paper, we study the hypothesis and determine the Turán numbers of k₁P_2l∪ k₂S_2l-1 when n is sufficiently large.

Related

• Some results on the Turán number of k₁P_ℓ∪ k₂S_ℓ-1
• The Turán number of path-star forests
• On the Turan number of forests
• The maximum number of stars in a graph without linear forest
• Turán numbers for disjoint paths