Bounds of a number of leaves of spanning trees

Abstract

We prove that every connected graph with $s$ vertices of degree not 2 has a spanning tree with at least $\frac{1}{4}(s-2)+2$ leaves. Let $G$ be a be a connected graph of girth $g$ with $v>1$ vertices. Let maximal chain of successively adjacent vertices of degree 2 in the graph $G$ does not exceed $k\ge 1$. We prove that $G$ has a spanning tree with at least ${\alpha }_{g,k}(v(G)-k-2)+2$ leaves, where ${\alpha }_{g,k}=\frac{[\frac{g+1}{2}]}{[\frac{g+1}{2}](k+3)+1}$ for $k<g-2$; ${\alpha }_{g,k}=\frac{g-2}{(g-1)(k+2)}$ for $k\ge g-2$. We present infinite series of examples showing that all these bounds are exact.

Misprints in Lemma 1 corrected, results unchanged

Cited by in corpus (3)

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