Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647644 | Discrete Mathematics | 2013 | 9 Pages |
Abstract
When GG is a graph with average degree greater than k−2k−2, Erdős and Gallai proved that GG contains a path on kk vertices. Erdős and Sós conjectured that under the same condition, GG should contain every tree on kk vertices. Several results based upon the number of vertices in GG have been proved including the special cases where GG has exactly kk vertices (Zhou), k+1k+1 vertices (Slater, Teo and Yap), k+2k+2 vertices (Woźniak) and k+3k+3 vertices (Tiner). To strengthen these results, we will prove that the Erdős-Sós conjecture holds when the graph GG contains no path with k+4k+4 vertices (no restriction is imposed on the number of vertices of GG).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Nancy Eaton, Gary Tiner,