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

Abstract

We prove that every connected graph with $s$ vertices of degree~1 and 3 and $t$ vertices of degree at least~4 has a spanning tree with at least $\frac{1}{3}t+\frac{1}{4}s+\frac{3}{2}$ leaves. We present infinite series of graphs showing that our bound is tight.

26 pages. Russian version: POMI Preprint 16/2011, http://www.pdmi.ras.ru/preprint/2011/11-16.html

References in corpus (2)

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

Cited by in corpus (2)

• Maximum nullity and zero forcing number on cubic graphs
• Expansion, divisibility and parity