2007/07/18 by Paul Bonsma, Bonsma, Paul, Florian Zickfeld +1
Computer Science · #05C05 #05C35 #05C85 #68R10 #Advanced Database Systems and Queries #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.0707.2760
openalex publication_date 2007/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 K4-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.75k) 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.