Closure for Spanning Trees with <i>k</i>-Ended Stems

• 作者: Zheng Yan
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: CLOSURE SPANNING Tree STEM k-End STEM
• 年，卷（期）: 2014,（3）
• 页码范围: 55-59
• 页数: 5页
• 分类号: O1

摘要

Let T be a tree. The set of leaves of Τ is denoted by Leaf(Τ). The subtree Τ—Leaf(Τ) of T is called the stem of Τ. A stem is called a k-ended stem if it has at most k-leaves in it. In this paper, we prove the following theorem. Let G be a connected graph and k≥2 be an integer. Let u and ν be a pair of nonadjacent vertices in G. Suppose that |NG(u)∪NG(v)|≥|G|-k-1. Then G has a spanning tree with k-ended stem if and only if G+uv has a spanning tree with k-ended stem. Moreover, the condition on |NG(u)∪NG(v)| is sharp.