The maximum number of stars in a graph without linear forest

Abstract

For two graphs $J$ and $H$, the generalized Turán number, denoted by $ex(n,J,H)$, is the maximum number of copies of $J$ in an $H$-free graph of order $n$. A linear forest $F$ is the disjoint union of paths. In this paper, we determine the number $ex(n,S_r,F)$ when $n$ is large enough and characterize the extremal graphs attaining $ex(n,S_r,F)$, which generalizes the results on $ex(n,S_r,P_k)$, $ex(n,K_2,(k+1)P_2)$ and $ex(n,K_{1,r}^{\ast },(k+1)P_2)$. Finally, we pose the problem whether the extremal graph for $ex(n,J,F)$ is isomorphic to that for $ex(n,S_r,F)$, where $J$ is any graph such that the number of $J$'s in any graph $G$ does not decrease by shifting operation on $G$.

14 pages, 2 figures