UAH > Math > Colloquia > 4/4/2008
A graph G is well-covered if every maximal independent set of vertices in G has the same cardinality. A graph G is a Zm-well-covered graph if |I1| ≡ |I2| (mod m) for all maximal independent sets I1 and I2 in V(G). The recognition problem of Zm-well-covered graphs is a co-NP-complete problem. A graph G belongs to class M(t) if G has exactly t different sizes of maximal independent sets. A graph belongs to class I(t) if G has exactly t different sizes of maximal independent sets with sizes r, r + 1, ..., r + (t − 1), for some r ∈ N. Here we present some properties and open problems for graphs in these classes.