Bounds of a~number of leaves of spanning trees

A. V. Bankevich ; D. V. Karpov

Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part III, Tome 391 (2011), pp. 18-34

Résumé

We prove that every connected graph with $s$ vertices of degree not 2 has a spanning tree with at least $\frac14(s-2)+2$ leaves. Let $G$ be a connected graph of girth $g$ with $v$ vertices. Let maximal chain of successively adjacent vertices of degree 2 in the graph $G$ does not exceed $k\ge1$. 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$; $\alpha_{g,k}(v(G)-k-2)+2$ for $k\ge g-2$. We present infinite series of examples showing that all these bounds are exact.