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 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. 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-Leaves Spanning Tree. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-78773-0_46 | LATIN |
Keywords | Field | DocType |
n vertex,certain subgraphs,cubic graph,diamond k4,max-leaves spanning tree,known time complexity,size m,simple fpt algorithm,spanning tree,minimum degree,form n,time complexity | Discrete mathematics,Combinatorics,Trémaux tree,Minimum degree spanning tree,k-minimum spanning tree,Euclidean minimum spanning tree,Spanning tree,Reverse-delete algorithm,Mathematics,Kruskal's algorithm,Minimum spanning tree | Conference |
Volume | ISSN | ISBN |
4957 | 0302-9743 | 3-540-78772-0 |
Citations | PageRank | References |
12 | 0.65 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Bonsma | 1 | 287 | 20.46 |
| Florian Zickfeld | 2 | 52 | 4.14 |