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.

Keywords

• spanning tree
• implicit degree
• leaves