Spanning trees with a bounded number of leaves in a claw-free graph

作者：Kano Mikio^*; Kyaw Aung; Matsuda Haruhide; Ozeki Kenta; Saito Akira; Yamashita Tomoki

来源：Ars Combinatoria, 2012, 103: 137-154.

• spanning tree
• leaf
• degree sum
• claw-free graphs

For a graph H and an integer k %26gt;= 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) %26gt;= vertical bar G vertical bar - k, then G has a spanning tree with at most k leaves. We also show that the bound vertical bar G vertical bar - k is sharp and discuss the maximum degree of the required spanning trees.

• 出版日期2012-1