Name
Abstract | ||
|---|---|---|
It is known that graphs on n vertices with minimum degree at least 3 have spanning trees with at least n/4+2 leaves and that this can be improved to (n+4)/3 for cubic graphs without the diamond K\"4-e as a subgraph. We generalize the second result by proving that every graph G without diamonds and certain subgraphs called blossoms has a spanning tree with at least (n\"=\"3(G)+4)/3 leaves, where n\"=\"3(G) is the number of vertices with degree at least 3 in G. We show that it is necessary to exclude blossoms in order to obtain a bound of the form n\"=\"3(G)/3+c. This bound is used to deduce new similar bounds. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.disc.2011.11.043 | Discrete Mathematics |
Keywords | Field | DocType |
lower bound,maximum number of leaves,spanning tree | Discrete mathematics,Graph,Combinatorics,Minimum degree spanning tree,Vertex (geometry),Of the form,Upper and lower bounds,Cubic graph,Spanning tree,Mathematics | Journal |
Volume | Issue | ISSN |
312 | 6 | 0012-365X |
Citations | PageRank | References |
1 | 0.36 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Bonsma | 1 | 287 | 20.46 |
| Florian Zickfeld | 2 | 52 | 4.14 |