Opuscula Math. 37, no. 4 (2017), 501-508
http://dx.doi.org/10.7494/OpMath.2017.37.4.501

Opuscula Mathematica

# Spanning trees with a bounded number of leaves

Junqing Cai
Evelyne Flandrin
Hao Li
Qiang Sun

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.

Keywords: spanning tree, implicit degree, leaves.

Mathematics Subject Classification: 05C07.

Full text (pdf)