The Turan Number of Disjoint Copies of Paths

2015/11/24 by Long‐Tu Yuan, Yuan, Long-Tu, Xiao‐Dong Zhang +1 · 3 citations
Computer Science · Mathematics · #05C35 #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1511.07679

openalex publication_date 2015/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Turán number of a graph H, ex(n,H), is the maximum number of edges in a simple graph of order n which does not contain H as a subgraph. Let k⋅ P₃ denote k disjoint copies of a path on 3 vertices. In this paper, we determine the value ex(n, k⋅ P₃) and characterize all extremal graphs. This extends a result of Bushaw and Kettle [N. Bushaw and N. Kettle, Turán Numbers of multiple and equibipartite forests, Combin. Probab. Comput., 20(2011) 837-853.], which solved the conjecture proposed by Gorgol in [I. Gorgol. Turán numbers for disjoint copies of graphs. \it Graphs Combin., 27 (2011) 661-667.].

Cited by

• Exact Turán numbers of two vertex-disjoint paths
• Turán number of four vertex-disjoint cliques
• Turán type problems for a fixed graph and a linear forest

Related

• Turán numbers for disjoint paths
• On the Turan number of forests
• Turán number of four vertex-disjoint cliques
• Turán numbers of vertex-disjoint cliques in r-partite graphs
• Turán Numbers for Forests of Paths in Hypergraphs