Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647901 | Discrete Mathematics | 2012 | 17 Pages |
Abstract
It is known that graphs on nn vertices with minimum degree at least 3 have spanning trees with at least n/4+2n/4+2 leaves and that this can be improved to (n+4)/3(n+4)/3 for cubic graphs without the diamond K4−eK4−e as a subgraph. We generalize the second result by proving that every graph GG without diamonds and certain subgraphs called blossoms has a spanning tree with at least (n≥3(G)+4)/3(n≥3(G)+4)/3 leaves, where n≥3(G)n≥3(G) is the number of vertices with degree at least 3 in GG. We show that it is necessary to exclude blossoms in order to obtain a bound of the form n≥3(G)/3+cn≥3(G)/3+c. This bound is used to deduce new similar bounds.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Paul Bonsma, Florian Zickfeld,