Spanning trees in a Claw-free graph whose stems have at most k branch vertices

2018/02/27 by Ha, Pham Hoang
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1802.09981

Abstract

Let T be a tree, a vertex of degree one and a vertex of degree at least three is called a leaf and a branch vertex, respectively. The set of leaves of T is denoted by Leaf(T). The subtree T-Leaf(T) of T is called the stem of T and denoted by Stem(T). In this paper, we give two sufficient conditions for a connected claw-free graph to have a spanning tree whose stem has a bounded number of branch vertices, and those conditions are best possible. As corollaries of main results we also give some conditions to show that a connected claw-free graph has a spanning tree whose stem is a spider.

Related

• Spanning trees of claw-free graphs with few leaves and branch vertices
• Spanning trees of a claw-free graph whose reducible stems have few leaves
• A note on spanning trees of connected K_1,t-free graphs whose stems have a few leaves
• Spanning trees with at most 2 branch vertices in claw - free graphs
• Spanning trees of K_1,4-free graphs with a bounded number of leaves and branch vertices