The generalized Turán number of spanning linear forests

Abstract

Let $\mathcal{F}$ be a family of graphs. A graph $G$ is called \textit{$\mathcal{F}$-free} if for any $F\in \mathcal{F}$, there is no subgraph of $G$ isomorphic to $F$. 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_{s,t}^{\ast }$ a graph obtained from $K_{s,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,K_s,{\mathcal{L}}_{n,k})$ and $ex(n,K_{s,t}^{\ast },{\mathcal{L}}_{n,k})$. Also, we study the case of this problem when the \textit{"host graph"} is bipartite. Denote by $e{x}_{bip}(n,T,\mathcal{F})$ the maximum possible number of copies of $T$ in an $\mathcal{F}$-free bipartite graph with each part of size $n$. We determine the exact value of $e{x}_{bip}(n,K_{s,t},{\mathcal{L}}_{n,k})$. Our proof is mainly based on the shifting method.

15 pages. 0 figure