Constructing trees in graphs with no K2,s |
| |
| Authors: | Suman Balasubramanian Edward Dobson |
| |
| Affiliation: | Department of Mathematics and Statistics, Mississippi State University, P.O. Drawer MA, Mississippi State, MS 39762 |
| |
| Abstract: | Let s ≥ 2 be an integer and k > 12(s ? 1) an integer. We give a necessary and sufficient condition for a graph G containing no K2,s with  and  to contain every tree T of order k + 1. We then show that every graph G with no K2,s and average degree greater than k ? 1 satisfies this condition, improving a result of Haxell, and verifying a special case of the Erd?s—Sós conjecture, which states that every graph of average degree greater than k ? 1 contains every tree of order k + 1. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 301–310, 2007 |
| |
| Keywords: | trees Erdő s— Só s conjecture K2,s |
|
|
