A note on independence number, connectivity and k-ended tree

2018/10/26 by Pham Hoang Ha, Ha, Pham Hoang
Computer Science · Mathematics · #05C05 #05C40 #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.1810.11242

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

Abstract

A k-ended tree is a tree with at most k leaves. In this note, we give a simple proof for the following theorem. Let G be a connected graph and k be an integer (k≥ 2). Let S be a vertex subset of G such that α_G(S) ≤ k + κ_G(S)- 1. Then, G has a k-ended tree which covers S. Moreover, the condition is sharp.

Related

• On large k-ended trees in connected graphs
• Progress on sufficient conditions for a graph to have a spanning k-ended tree
• Spectral condition for spanning k-ended trees in t-connected graphs
• On k-ended spanning and dominating trees
• Spanning k-ended trees of 3-regular connected graphs