Spanning Trees Whose Stems Have at Most \(k\) Leaves

Abstract

For a tree \(T\), the set of leaves of \(T\) is denoted by \(Leaf(T)\), and the subtree \(T – Leaf(T)\) is called the \({stem} of T\). We prove that if a connected graph \(G\) either satisfies \(\sigma_{k+1}(G) \geq |G| – k – 1\) or has no vertex set of size \(k+1\) such that the distance between any two of its vertices is at least \(4\), then \(G\) has a spanning tree whose stem has at most \(k\) leaves, where \(\sigma_{k+1}(G)\) denotes the minimum degree sum of \(k+1\) independent vertices of \(G\). Moreover, we show that the condition on \(\sigma_{k+1}(G)\) is sharp. Additionally, we provide another similar sufficient degree condition for a claw-free graph to have such a spanning tree.