Spanning trees with at most 4 leaves in K_1,5-free graphs

2018/04/25 by Yuan Chen, Chen, Yuan, Pham Hoang Ha +3
Computer Science · Mathematics · #05C05 #05C07 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1804.09332

openalex publication_date 2018/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In 2009, Kyaw proved that every n-vertex connected K_1,4-free graph G with σ₄(G)≥ n-1 contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw's result for connected K_1,5-free graphs. We show that every n-vertex connected K_1,5-free graph G with σ₅(G)≥ n-1 contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition `σ₅(G)≥ n-1' is best possible.

Related

• Spanning trees with at most 5 leaves and branch vertices in total of K_1,5-free graphs
• Spanning trees of K_1,4-free graphs with a bounded number of leaves and branch vertices
• Spanning trees with at most 2 branch vertices in claw - free graphs
• A note on spanning trees of connected K_1,t-free graphs whose stems have a few leaves
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms