Spanning trees of a claw-free graph whose reducible stems have few leaves

2021/12/08 by Pham Hoang Ha, Ha, Pham Hoang
Computer Science · #05C05 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2112.04102

openalex publication_date 2021/12/08 · openalex created_date 2021/12/31 · openalex updated_date 2026/07/28

Abstract

Let T be a tree, a vertex of degree one is a leaf of T and a vertex of degree at least three is a branch vertex of T. For two distinct vertices u,v of T, let P_T[u,v] denote the unique path in T connecting u and v. For a leaf x of T, let y_x denote the nearest branch vertex to x. For every leaf x of T, we remove the path P_T [x, y_x) from T, where P_T [x, y_x) denotes the path connecting x to y_x in T but not containing y_x. The resulting subtree of T is called the \it reducible stem of T. In this paper, we first use a new technique of Gould and Shull to state a new short proof for a result of Kano et al. on the spanning tree with a bounded number of leaves in a claw-free graph. After that, we use that proof to give a sharp sufficient condition for a claw-free graph having a spanning tree whose reducible stem has few leaves.

Related

• Spanning trees in a Claw-free graph whose stems have at most k branch vertices
• Spanning trees of claw-free graphs with few leaves and branch vertices
• Spanning trees of K_1,4-free graphs 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