Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
7  
There's a related paper here (portal.acm.org/citation.cfm?id=303085) that suggests that the problem of determining this for a given graph is co-NP-complete, and so characterizing the property will be tricky –  Suresh Venkat Aug 7 '11 at 2:32
    
Thank you for the reference! –  laszlo kozma Aug 8 '11 at 9:18

2 Answers 2

up vote 26 down vote accepted

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."

share|improve this answer
    
Thank you, this is exactly what I was looking for. Searching for "well-covered graphs" I found many more references. –  laszlo kozma Aug 8 '11 at 9:19

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.

share|improve this answer
6  
"It will be interesting to understand graphs where this property holds for all induced subgraphs". Unless I am mistaken, a (connected) graph and every of its induced subgraphs are well-covered iff it is a complete graph, since the path $P_3$ with 3 vertices and 2 edges is not well-covered. –  user13136 Feb 22 '13 at 18:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.