The generalized Turán number of spanning linear forests (Q2115153)

Given a graph \(T\) and a family of graphs \(\mathcal {F}\), the generalized Turán number of \(\mathcal {F}\) is the maximum number of copies of \(T\) in an \(\mathcal {F}\)-free graph on \(n\) vertices, denoted by \(ex(n, T, \mathcal {F})\). A linear forest is a graph whose connected components are all paths or isolated vertices. Let \(\mathcal{L}_{n,k}\) be the family of all linear forests of order \(n\) with \(k\) edges and \(K^{\ast}_{ s,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, the authors determine the exact values of \(ex(n,K_s,\mathcal{L}_{n,k})\) and \(ex(n,K^{\ast}_{s,t},\mathcal{L}_{n,k})\) and study the case of this problem when the ``host graph'' is bipartite. They also determine the exact value of the maximum possible number of copies of \(K_{s,t}\) in an \(\mathcal{L}_{n,k}\)-free bipartite graph with each part of size \(n\). The proof is mainly based on the shifting method (also known as Kelmans transformation [\textit{A. K. Kelmans}, Acta Math. Acad. Sci. Hung. 37, 77--88 (1981; Zbl 0503.05056)]).