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

作者：Matsuda Haruhide; Ozeki Kenta^*; Yamashita Tomoki

来源：Graphs and Combinatorics, 2014, 30(2): 429-437.

DOI：10.1007/s00373-012-1277-5

• Spanning trees
• Branch vertices
• Claw-free graphs

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n - 2. These conditions are best possible. A related conjecture also is proposed.

• 出版日期2014-3