Article ID Journal Published Year Pages File Type
419494 Discrete Applied Mathematics 2011 6 Pages PDF
Abstract

A graph is well-covered if every maximal independent set has the same cardinality. The recognition problem of well-covered graphs is known to be co-NP-complete. Let ww be a linear set function defined on the vertices of GG. Then GG is ww-well-covered   if all maximal independent sets of GG are of the same weight. The set of weight functions ww for which a graph is ww-well-covered is a vector space  . We prove that finding the vector space of weight functions under which an input graph is ww-well-covered can be done in polynomial time, if the input graph contains neither C4C4 nor C5C5 nor C6C6 nor C7C7.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,