Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree~3 and at least~4

Abstract

We prove, that every connected graph with $s$ vertices of degree 3 and $t$ vertices of degree at least~4 has a spanning tree with at least $\frac{2}{5}t+\frac{1}{5}s+\alpha$ leaves, where $\alpha \ge \frac{8}{5}$. Moreover, $\alpha \ge 2$ for all graphs besides three exclusions. All exclusion are regular graphs of degree~4, they are explicitly described in the paper. We present infinite series of graphs, containing only vertices of degrees~3 and~4, for which the maximal number of leaves in a spanning tree is equal for $\frac{2}{5}t+\frac{1}{5}s+2$. Therefore we prove that our bound is tight.

33 pages, 15 figures

References in corpus (1)

• Bounds of a number of leaves of spanning trees

Cited by in corpus (1)

• Spanning trees with many leaves: lower bounds in terms of number of vertices of degree 1, 3 and at least~4