Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418925 | Discrete Applied Mathematics | 2015 | 10 Pages |
A graph GG is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function ww is defined on its vertices. Then GG is ww-well-covered if all maximal independent sets are of the same weight, where a weight of a set is the sum of weights of its elements. For every graph GG, the set of weight functions ww such that GG is ww-well-covered is a vector space . Given an input graph GG without cycles of lengths 4, 5, and 6, we characterize polynomially the vector space of weight functions ww for which GG is ww-well-covered.Let BB be an induced complete bipartite subgraph of GG on vertex sets of bipartition BXBX and BYBY. Assume that there exists an independent set SS such that each of S∪BXS∪BX and S∪BYS∪BY is a maximal independent set of GG. Then BB is a generating subgraph of GG, and it produces the restriction w(BX)=w(BY)w(BX)=w(BY). It is easy to see that for every weight function ww, if GG is ww-well-covered, then the above restriction is satisfied.In the special case, where BX={x}BX={x} and BY={y}BY={y}, we say that xyxy is a relating edge. Recognizing relating edges and generating subgraphs is an NP-complete problem. However, we provide a polynomial algorithm for recognizing generating subgraphs of an input graph without cycles of lengths 5, 6 and 7. We also present a polynomial algorithm for recognizing relating edges in an input graph without cycles of lengths 5 and 6.