The maximum number of stars in a graph without linear forest

2021/12/25 by Sumin Huang, Huang, Sumin, Jianguo Qian +1
Computer Science · Mathematics · #05C30 #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2112.13202

openalex publication_date 2021/12/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For two graphs J and H, the generalized Turán number, denoted by ex(n,J,H), is the maximum number of copies of J in an H-free graph of order n. A linear forest F is the disjoint union of paths. In this paper, we determine the number ex(n,S_r,F) when n is large enough and characterize the extremal graphs attaining ex(n,S_r,F), which generalizes the results on ex(n, S_r, P_k), ex(n,K₂,(k+1) P₂) and ex(n,K^*_1,r,(k+1) P₂). Finally, we pose the problem whether the extremal graph for ex(n,J,F) is isomorphic to that for ex(n,S_r,F), where J is any graph such that the number of J's in any graph G does not decrease by shifting operation on G.

Related

• The Turán number of path-star forests
• Generalized Turán number for linear forests
• Turán numbers for hypergraph star forests
• Turán problems for linear forests and cliques
• On the Turan number of forests