Turán numbers for disjoint paths

Abstract

The Turán number of a graph $H$, $ex(n,H)$, is the maximum number of edges in any graph of order $n$ which does not contain $H$ as a subgraph. Lidický, Liu and Palmer determined $ex(n,F_m)$ for $n$ sufficiently large and proved that the extremal graph is unique, where $F_m$ is disjoint paths of $P_{k_1},\dots ,P_{k_m}$ [Lidický,B., Liu,H. and Palmer,C. (2013). On the Turán number of forests. Electron. J. Combin. 20(2) Paper 62, 13 pp]. In this paper, by mean of a different approach, we determine $ex(n,F_m)$ for all integers $n$ with minor conditions, which extends their partial results. Furthermore, we partly confirm the conjecture proposed by Bushaw and Kettle for $ex(n,k\cdot P_l)$ [Bushaw,N. and Kttle,N. (2011) Turán numbers of multiple paths and equibipartite forests. Combin. Probab. Comput. 20 837-853]. Moreover, we show that there exist two family graphs $F_m$ and $F_m^{\prime }$ such that $ex(n,F_m)=ex(n,F_m^{\prime })$ for all integers $n$, which is related to an old problem of Erdős and Simonovits.

19 pages