Spanning trees with a bounded number of leaves in a claw-free graph. (English) Zbl 1265.05100

Kano, M.; Kyaw, A.; Matsuda, H.; Ozeki, K.; Saito, A.; Yamashita, T.

Ars Comb. 103, 137-154 (2012).

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

Keywords:

spanning tree; leaf; degree sum; claw-free graph