Independence Numbers in Trees

• 作者: Jenq-Jong Lin Min-Jen Jou
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: INDEPENDENT SET INDEPENDENCE NUMBER TREE
• 年，卷（期）: 2015,（3）
• 页码范围: 27-31
• 页数: 5页
• 分类号: O1

摘要

The independence number of a graph G is the maximum cardinality among all independent sets of G. For any tree T of order n ≥ 2, it is easy to see that . In addition, if there are duplicated leaves in a tree, then these duplicated leaves are all lying in every maximum independent set. In this paper, we will show that if T is a tree of order n ≥ 4 without duplicated leaves, then . Moreover, we constructively characterize the extremal trees T of order n ≥ 4, which are without duplicated leaves, achieving these upper bounds.