2020/09/01 by Lin-Peng Zhang, Zhang, Lin-Peng, Ligong Wang +3
Computer Science · Mathematics · #05C05 #05C35 #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.2009.00181
openalex publication_date 2020/09/01 · openalex created_date 2020/09/08 · openalex updated_date 2026/07/28
Let F be a family of graphs. A graph G is called \textitF-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 Ln,k be the family of all linear forests of order n with k edges and K^*s,t a graph obtained from Ks,t by substituting the part of size s with a clique of the same size. In this paper, we determine the exact values of ex(n,Ks,Ln,k) and ex(n,K^*s,t,Ln,k). Also, we study the case of this problem when the "host graph" is bipartite. Denote by exbip(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 exbip(n,Ks,t,Ln,k). Our proof is mainly based on the shifting method.