Stability of generalized Turán number for linear forests

2022/11/15 by Xue, Yisai, Liu, Yichong, Kang, Liying
#05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2211.07822

Abstract

Given a graph T and a family of graphs F, the generalized Turán number of F is the maximum number of copies of T in an F-free graph on n vertices, denoted by ex(n,T,F). When T = K_r, ex(n, K_r, F) is a function specifying the maximum possible number of r-cliques in an F-free graph on n vertices. A linear forest is a forest whose connected components are all paths and isolated vertices. Let L_k be the family of all linear forests of size k without isolated vertices. In this paper, we obtained the maximum possible number of r-cliques in G, where G is L_k-free with minimum degree at least d. Furthermore, we give a stability version of the result. As an application of the stability version of the result, we obtain a clique version of the stability of the Erdős-Gallai Theorem on matchings.

Related

• Turán problems for linear forests and cliques
• Generalized Turán number for linear forests
• The generalized Turán number of spanning linear forests
• Turán type problems for a fixed graph and a linear forest
• The Turán problem for a family of tight linear forests