×

zbMATH — the first resource for mathematics

Spanning trees with a bounded number of leaves in a claw-free graph. (English) Zbl 1265.05100
Summary: 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.

MSC:
05C05 Trees
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite