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

Abstract

For a graph $H$ and an integer $k\ge 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)\ge |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.