Spanning \(k\)-ended trees of a claw-free graph. (English) Zbl 1358.05062

Summary: For a tree \(T\), a vertex of \(T\) with degree one is often called a leaf of \(T\). Let \(k\geq2\) be an integer. We prove that if a connected claw-free graph \(G\) satisfies \(\alpha^3(G)\leq k\), then \(G\) has a spanning tree having at most \(k\) leaves, where \(\alpha^3(G)\) denotes the maximum number of vertices of \(G\) that are pairwise distance at least three in \(G\). This result implies a known result proved by M. Kano et al. [Ars Comb. 103, 137–154 (2012; Zbl 1265.05100)] which states that if the minimum degree sum of independent \(k+1\) vertices of a connected claw-free graph \(G\) is at least \(|G|-k\), then \(G\) has a spanning \(k\)-ended tree. The condition on \(\alpha^3(G)\) is sharp.


05C05 Trees


Zbl 1265.05100
Full Text: DOI