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

PDF
420kB 
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 (2nD+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 MaxLeaf 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