Maximal independent sets in caterpillar graphs

被引：10
作者：
Ortiz, Carmen [2 ]
Villanueva, Monica [1 ]
机构：
[1] Univ Santiago Chile, Fac Engn, Santiago, Chile
[2] Adolfo Ibanez Univ, Fac Sci & Engn, Santiago, Chile
来源：
DISCRETE APPLIED MATHEMATICS | 2012年 / 160卷 / 03期
关键词：
Graph algorithms; Caterpillar graph; Enumeration of maximal independent sets; Intersection graph; Independent graph; Clique graph; NUMBER; ALGORITHM; GENERATE; FAMILY;
D O I：
10.1016/j.dam.2011.10.024
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A caterpillar graph is a tree in which the removal of all pendant vertices results in a chordless path. In this work, we determine the number of maximal independent sets (mis) in caterpillar graphs. For a general graph, this problem is #P-complete. We provide a polynomial time algorithm to generate the whole family of mis in a caterpillar graph. We also characterize the independent graph (intersection graph of mis) and the clique graph (intersection graph of cliques) of complete caterpillar graphs. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码：259 / 266
页数：8
相关论文
共 31 条
[21]   Counting the number of independent sets in chordal graphs [J].
Okamoto, Yoshio ;
Uno, Takeaki ;
Uehara, Ryuhei .
JOURNAL OF DISCRETE ALGORITHMS, 2008, 6 (02) :229-242
[22]   The number of independent sets in unicyclic graphs [J].
Pedersen, AS ;
Vestergaard, PD .
DISCRETE APPLIED MATHEMATICS, 2005, 152 (1-3) :246-256
[23]  
Sagan B. E., 1988, SIAM J DISCRETE MATH, V1, P105, DOI DOI 10.1137/0401012
[24]   Maximal and maximum independent sets in graphs with at most r cycles [J].
Sagan, Bruce E. ;
Vatter, Vincent R. .
JOURNAL OF GRAPH THEORY, 2006, 53 (04) :283-314
[25]  
Szwarcfiter J.L., 2003, Recent Advances in Algorithms and Combinatorics, P109
[26]  
Tsukiyama S., 1977, SIAM Journal on Computing, V6, P505, DOI 10.1137/0206036
[27]  
Valiant L. G., 1979, Theoretical Computer Science, V8, P189, DOI 10.1016/0304-3975(79)90044-6
[28]   THE NUMBER OF MAXIMAL INDEPENDENT SETS IN A TREE [J].
WILF, HS .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (01) :125-130
[29]   Trees with extremal numbers of maximal independent sets including the set of leaves [J].
Wloch, Iwona .
DISCRETE MATHEMATICS, 2008, 308 (20) :4768-4772
[30]   Maximal independent sets in graphs with at most r cycles [J].
Ying, Goh Chee ;
Meng, Koh Khee ;
Sagan, Bruce E. ;
Vatter, Vincent R. .
JOURNAL OF GRAPH THEORY, 2006, 53 (04) :270-282
1234