Spanning trees with a bounded number of leaves

Abstract

In 1998, H. Broersma and H. Tuinstra proved that: Given a connected graph $G$ with $n\geq 3$ vertices, if $d(u)+d(v)\geq n-k+1$ for all non-adjacent vertices u and v of $G(k\geq 1)$, then $G$ has a spanning tree with at most $k$ leaves. In this paper, we generalize this result by using implicit degree sum condition of $t$($2\leq t\leq k$) independent vertices and we prove what follows: Let $G$ be a connected graph on $n\geq 3$ vertices and $k\geq 2$ be an integer. If the implicit degree sum of any $t$ independent vertices is at least $\frac{t(n-k)}{2}+1$ for ($k\geq t\geq 2$), then $G$ has a spanning tree with at most $k$ leaves.