|   | 
Author Ortiz, C.; Villanueva, M.
Title Maximal independent sets in caterpillar graphs Type
Year 2012 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.
Volume 160 Issue 3 Pages 259-266
Keywords Graph algorithms; Caterpillar graph; Enumeration of maximal independent sets; Intersection graph; Independent graph; Clique graph
Abstract 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.
Address [Villanueva, Monica] Univ Santiago Chile, Fac Engn, Santiago, Chile, Email: monica.villanueva@usach.cl
Corporate Author Thesis (down)
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000299144900009 Approved
Call Number UAI @ eduardo.moreno @ Serial 190
Permanent link to this record