Turàn numbers of Multiple Paths and Equibipartite Trees

Abstract

The Turán number of a graph H, ex(n;H), is the maximum number of edges in any graph on n vertices which does not contain H as a subgraph. Let P_l denote a path on l vertices, and kP_l denote k vertex-disjoint copies of P_l. We determine ex(n, kP_3) for n appropriately large, answering in the positive a conjecture of Gorgol. Further, we determine ex (n, kP_l) for arbitrary l, and n appropriately large relative to k and l. We provide some background on the famous Erdős-Sós conjecture, and conditional on its truth we determine ex(n;H) when H is an equibipartite forest, for appropriately large n.

17 pages, 13 figures; Updated to incorporate referee's suggestions; minor structural changes

Cited by in corpus (9)

• The formula for Turán number of spanning linear forests
• Extremal graphs for the odd prism
• On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees
• On the anti-Ramsey number of forests
• Erdos-Gallai Stability Theorem for Linear Forests
• Anti-Ramsey numbers of paths and cycles in hypergraphs
• On the anti-Ramsey numbers of linear forests
• The signless Laplacian spectral radius of graphs with forbidding linear forests
• On the Turan number of forests