Spanning trees with at most 5 leaves and branch vertices in total of K_1,5-free graphs

2022/07/09 by Pham Hoang Ha, Ha, Pham Hoang, Nguyen Hoang Trang +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2207.04170

openalex publication_date 2022/07/09 · openalex created_date 2022/07/13 · openalex updated_date 2026/07/28

Abstract

In this paper, we prove that every n-vertex connected K_1,5-free graph G with σ₄(G)≥ n-1 contains a spanning tree with at most 5 leaves and branch vertices in total. Moreover, the degree sum condition "σ₄(G)≥ n-1" is best possible.

Related

• Spanning trees with at most 4 leaves in 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 few branch vertices