Maximal independent sets in graphs with at most one cycle

被引：35
作者：
Jou, MJ [1 ]
Chang, GJ [1 ]
机构：
[1] NATL CHIAO TUNG UNIV,DEPT MATH APPL,HSINCHU 30050,TAIWAN
来源：
DISCRETE APPLIED MATHEMATICS | 1997年 / 79卷 / 1-3期
关键词：
(maximal) independent set; cycle; connected graph; isolated vertex; leaf; baton;
D O I：
10.1016/S0166-218X(97)00033-4
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we determine the largest number of maximal independent sets among all connected graphs of order n, which contain at most one cycle. We also characterize those extremal graphs achieving this maximum value. As a consequence, the corresponding results for graphs with at most one cycle but not necessarily connected are also given.
引用
收藏
页码：67 / 73
页数：7
相关论文
共 50 条
12345