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 条

[1]

Aho A. V., 1972, SIAM Journal on Computing, V1, P131, DOI 10.1137/0201008

[2]

Chang GJ, 1999, DISCRETE MATH, V197, P169

[3]

Coja-Oghlan A., 2003, 6 WORKSH MOD ALG PLA, P48

[4] Object recognition as many-to-many feature matching [J].