Spanning trees with a bounded number of leaves - Junqing Cai (Opuscula Mathematica, 2017)
In 1998, H. Broersma and H. Tuinstra proved that: Given a connected graph \(G\) with \(n≥ 3\) vertices, if \(d(u)+d(v)≥ n-k+1\) for all non-adjacent vertices \(u\) and \(v\) of \(G\) (\(k≥ 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≤ t≤ k\)) independent vertices and we prove what follows: Let \(G\) be a connected graph on \(n≥ 3\) vertices and \(k≥ 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≥ t≥ 2\)), then \(G\) has a spanning tree with at most \(k\) leaves.