Spanning trees with at most 2 branch vertices in claw - free graphs

2018/06/03 by Pham Hoang Ha, Ha, Pham Hoang, Dang Dinh Hanh +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1806.00734

openalex publication_date 2018/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this article, we will prove that if G is a connected claw-free graph and either σ₆(G)≥ |G|-5 or σ₇(G)≥ |G|-2, here σ_k(G) is the minimmum degree sum of k independent vertices in G, then G has a spanning tree with at most two branch vertices.

Related

• Spanning trees of claw-free graphs with few leaves and branch vertices
• Spanning trees in a Claw-free graph whose stems have at most k branch vertices
• Spanning trees with at most 5 leaves and branch vertices in total of K_1,5-free graphs
• Spanning trees of a claw-free graph whose reducible stems have few leaves
• Spanning trees with at most 4 leaves in K_1,5-free graphs