The Turán Number for Spanning Linear Forests

2018/07/05 by Jian Wang, Weihua Yang, Wang, Jian +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1807.01825

openalex publication_date 2018/07/05 · openalex created_date 2018/07/10 · openalex updated_date 2026/07/28

Abstract

For a set of graphs F, the extremal number ex(n;F) is the maximum number of edges in a graph of order n not containing any subgraph isomorphic to some graph in F. If F contains a graph on n vertices, then we often call the problem a spanning Turán problem. A linear forest is a graph whose connected components are all paths and isolated vertices. In this paper, we let L_n^k be the set of all linear forests of order n with at least n-k+1 edges. We prove that when n≥ 3k and k≥ 2, ex(n;L_n^k)=\binomn-k+12+ O(k²). Clearly, the result is interesting when k=o(n).

Related

• Generalized Turán number for linear forests
• The generalized Turán number of spanning linear forests
• On the Turan number of forests
• Turán problems for linear forests and cliques
• Turán type problems for a fixed graph and a linear forest