Turàn numbers of Multiple Paths and Equibipartite Trees

Details Turàn numbers of Multiple Paths and Equibipartite Trees Turàn numbers of Multiple Paths and Equibipartite Trees

2011-06-29

arxiv.org/abs/1106.5904v2

Combinatorics, Probability and Computing 20 (2011), 837 - 853

Mathematics

Combinatorics

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

Scientific paper

10.1017/S0963548311000460

The Tur\'an 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\H{o}s-S\'os conjecture, and conditional on its truth we determine ex(n;H) when H is an equibipartite forest, for appropriately large n.

Affiliated with

Also associated with

No associations

Rating

Turàn numbers of Multiple Paths and Equibipartite Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Turàn numbers of Multiple Paths and Equibipartite Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Turàn numbers of Multiple Paths and Equibipartite Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-359206