Spanning Trees with Many Leaves in Graphs With Minimum Degree Three

Abstract

We present two lower bounds for the maximum number of leaves over all spanning trees of a graph. For connected, triangle-free graphs on n vertices, with minimum degree at least three, we show that a spanning tree with at least $(n+4)/3$ leaves exists. For connected graphs with minimum degree at least three, without diamonds induced by vertices of degree three, we show that a spanning tree with at least $(2n+12)/7$ leaves exists. (A diamond is a $K_4$ minus one edge.) 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 that find spanning trees satisfying the bounds are given.