16 citations · 16 across the 2 of their papers we have counts for
2 papers
cs.DS2007★ 16 cited
An FPT Algorithm for Directed Spanning k-Leaf
Paul Bonsma, Frederic Dorn
An out-branching of a directed graph is a rooted spanning tree with all arcs directed outwards from the root. We consider the problem of deciding whether a given directed graph D h…
math.CO2007
Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
Paul Bonsma, Florian Zickfeld
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 withou…