Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
| dc.creator | Bonsma, Paul | |
| dc.creator | Zickfeld, Florian | |
| dc.date | 2007-07-18 | |
| dc.date.accessioned | 2026-07-07T08:19:04Z | |
| dc.date.available | 2026-07-07T08:19:04Z | |
| dc.description | 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 with minimum degree at least 3, without diamonds and certain subgraphs called blossoms, has a spanning tree with at least (n+4)/3 leaves, and generalize this further by allowing vertices of lower degree. We show that it is necessary to exclude blossoms in order to obtain a bound of the form n/3+c. We use the new bound to obtain a simple FPT algorithm, which decides in O(m)+O^*(6.75^k) time whether a graph of size m has a spanning tree with at least k leaves. This improves the best known time complexity for MAX LEAF SPANNING TREE. | |
| dc.description | 25 pages, 27 Figures | |
| dc.identifier | https://arxiv.org/abs/0707.2760 | |
| dc.identifier | http://arxiv.org/abs/0707.2760 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134644 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C05; 05C35; 05C85; 68R10 | |
| dc.title | Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms | |
| dc.type | text |