The Turán number for spanning linear forests.

Abstract For a set of graphs F , the extremal number e x (n ; F) is the maximum number of edges in a graph of order n not containing any subgraph isomorphic to some graph in F. If F contains a graph on n vertices, then we often call the problem a spanning Turán problem. A linear forest is a graph whose connected components are all paths and isolated vertices. In this paper, we let L n k be the set of all linear forests of order n with at least n − k + 1 edges. We prove that when n ≥ 3 k and k ≥ 2 , e x (n ; L n k) = n − k + 1 2 + O (k 2). Clearly, the result is interesting when k = o (n). [ABSTRACT FROM AUTHOR]