Generalized Tur{a}n number for linear forests


Abstract in English

The generalized Tur{a}n number $ex(n,K_s,H)$ is defined to be the maximum number of copies of a complete graph $K_s$ in any $H$-free graph on $n$ vertices. Let $F$ be a linear forest consisting of $k$ paths of orders $ell_1,ell_2,...,ell_k$. In this paper, by characterizing the structure of the $F$-free graph with large minimum degree, we determine the value of $ex(n,K_s,F)$ for $n=Omegaleft(|F|^sright)$ and $kgeq 2$ except some $ell_i=3$, and the corresponding extremal graphs. The special case when $s=2$ of our result improves some results of Bushaw and Kettle (2011) and Lidick{y} et al. (2013) on the classical Tur{a}n number for linear forests.

Download