Spanning trees with many leaves: new extremal results and an improved FPT algorithm

Share/Save/Bookmark

Bonsma, P.S. (2006) Spanning trees with many leaves: new extremal results and an improved FPT algorithm. [Report]

[img]
Preview
PDF
410Kb
Abstract:We present two lower bounds for the maximum number of leaves in a spanning tree of a graph. For connected graphs without triangles, with minimum degree at least three, we show that a spanning tree with at least (n+4)/3 leaves exists, where n is the number of vertices of the graph. For connected graphs with minimum degree at least three, that contain D diamonds induced by vertices of degree three (a diamond is a K4 minus one edge), we show that a spanning tree exists with at least (2n-D+12)/7 leaves. The proofs use the fact that spanning trees with many leaves correspond to small connected dominating sets. Both of these bounds are best possible for their respective graph classes. For both bounds simple polynomial time algorithms are given that find spanning trees satisfying the bounds.

The second bound is used to find a new fastest FPT algorithm for the Max-Leaf Spanning Tree problem. This problem asks whether a graph G on n vertices has a spanning tree with at least k leaves. The time complexity of our algorithm is f(k)g(n), where g(n) is a polynomial, and f(k) Î O(8.12k).


Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/66582
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 237578