Lower bounds on the number of leaves in spanning trees

D. V. Karpov

Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 62-73

Résumé

Let $G$ be a connected graph on $n\ge2$ vertices with girth at least $g$. Let maximal chain of successively adjacent vertices of degree 2 in the graph $G$ does not exceed $k\ge1$. Denote by $u(G)$ the maximal number of leaves in a spanning tree of $G$. We prove, that $u(G)\ge\alpha_{g,k}(v(G)-k-2)+2$, where $\alpha_{g,1}=\frac{[\frac{g+1}2]}{4[\frac{g+1}2]+1}$ and $\alpha_{g,k}=\frac1{2k+2}$ for $k\ge2$. We present infinite series of examples showing that all these bounds are tight.