toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author Ortiz, C.; Villanueva, M. pdf  doi
  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:  
  Corporate Author Thesis  
  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 (up)  
  Area Expedition Conference  
  Notes WOS:000299144900009 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 190  
Permanent link to this record
Select All    Deselect All
 |   | 

Save Citations:
Export Records: