Spanning Trees with a Bounded Number of Leaves in a Claw-Free Graph

Abstract

For a graph \(H\) and an integer \(k \geq 2\), let \(\sigma_k(H)\) denote the minimum degree sum of \(k\) independent vertices of \(H\). We prove that if a connected claw-free graph \(G\) satisfies \(\sigma_{k+1}(G) \geq |G| – k\), then \(G\) has a spanning tree with at most \(k\) leaves. We also show that the bound \(|G| – k\) is sharp and discuss the maximum degree of the required spanning trees.