Maximal/maximum independent sets

Question

Is there something known about the class of graphs with the property that all maximal independent sets have the same cardinality and are therefore maximum ISs?

For example, take a set of points in the plane and consider the graph of intersections among all segments between pairs of points in the set. (segments->vertices, intersections->edges). This graph will have the above property, as all maximal ISs correspond to triangulations of the original point set. Are there other categories of graphs known to have this property? Can this property be easily tested?

Answer 1

Such graphs are called well-covered graphs. Here is a recent paper on the subject that lists several useful references. As Suresh mentioned, the recognition problem is co-NP-complete.

Note that the independent sets of a graph form an abstract simplicial complex. Simplicial complexes that arise in this way are called "independence complexes" or "flag complexes." A simplicial complex is said to be pure if every maximal simplex has the same cardinality. So you may find some relevant papers by searching for "pure independence complex" or "pure flag complex."

Answer 2

The property MAXIMAL=MAXIMUM fo independent sets in graphs and more general combinatorial structures is important. It will be interesting to understand graphs where this property holds for all induced subgraphs. One general abstract case where we have MAXIMUM=MAXIMAL is when there is an underlying matroid structure, but there are many other cases, like the case of maximal planar graphs mentioned in the question. Here is a related example: Consider n points in the plane in convex position and let k be an integer. Consider graphs whose vertices are line segments between these points where two vertices are adjacent if the line segments do not cross. Dress proved that for this graph MAXIMIM=MAXIMAL for independent sets.