The Generalized Turán Number of Spanning Linear Forests

Let F be a family of graphs. A graph G is called F-free if for any F∈ F, there is no subgraph of G isomorphic to F. 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). A linear forest is a graph whose connected components are all paths or isolated vertices. Let L_n,k be the family of all linear forests of order n with k edges and Ks,t∗ be a graph obtained from K_s,t by substituting the part of size s with a clique of order s. In this paper, we determine the exact values of ex(n, K_s, L_n,k) and ex(n,Ks,t∗,Ln,k). Also, we study the case of this problem when the “host graph” is bipartite. Denote by ex_bip(n, T, F) the maximum possible number of copies of T in an F-free bipartite graph with each part of size n. We determine the exact value of ex_bip(n, K_s,t, L_n,k). Our proof is mainly based on the shifting method.