M-dominating k-ended trees of l-connected graphs. Issue 3 (1st December 2017)

• Record Type: Journal Article
• Authors: Tsugaki, Masao; Yan, Guiying
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 14:Issue 3(2017)
• Page Start: 277
• Page End: 286
• Publication Date: 2017-12-01
• Subjects: Vertex dominating -- m-dominating -- k-ended tree
• DOI: 10.1016/j.akcej.2017.04.004
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: Let k ≥ 2, l ≥ 1 and m ≥ 0 be integers, and let G be an l -connected graph. If there exists a subgraph X of G such that the distance between v and X is at most m for any v ∈ V ( G ), then we say that X m -dominates G . A subset S of V ( G ) is said to be 2 ( m + 1 ) -stable if the distance between each pair of distinct vertices in S is at least 2 ( m + 1 ) . In this paper, we prove that if G does not have a 2 ( m + 1 ) -stable set of order at least k + l, then G has an m -dominating tree which has at most k leaves.