A Note on Leaf-constrained Spanning Trees in a Graph

Abstract

An independent set $S$ of a connected graph $G$ is called a \emph{frame} if $G–S$ is connected. If $|S|=k$, then $S$ is called a \emph{k-frame}. We prove the following theorem.
Let $k\ge 2$ be an integer, $G$ be a connected graph with $V(G)=\{v_1,v_2,\dots ,v_n\}$, and ${\mathrm{deg}}_G(u)$ denote the degree of a vertex $u$. Suppose that for every $3$-frame $S=\{v_a,v_b,v_c\}$ such that $1\le a\le b\le c\le n$, ${\mathrm{deg}}_G(v_c)\le a$, ${\mathrm{deg}}_G(v_b)\le b-1$, and ${\mathrm{deg}}_G(v_c)\le c–2$, it holds that$${\mathrm{deg}}_G(v_a)+{\mathrm{deg}}_G(v_b)+{\mathrm{deg}}_G(v_c)–|N(v_a)\cap N(v_b)\cap N(v_c)|\ge |G|–k+1.$$ Then $G$ has a spanning tree with at most $k$-leaves. Moreover, the condition is sharp.
This theorem is a generalization of the results of E. Flandrin, H.A. Jung, and H. Li (Discrete Math. $90(1991),41-52)$ and of A. Kyaw (Australasian Journal of Combinatorics. $37(2007),3-10)$ for traceability.