<p>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.</p>

CC BY-SA 3.0
2013-02-22T18:55:53.543Z
"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
CC BY-SA 3.0
2013-01-01T09:10:43.377Z
2013-01-01T09:10:43.377Z
Gil Kalai
<p>Such graphs are called <i>well-covered</i> graphs.  <a href="http://arxiv.org/abs/1104.4556">Here</a> is a recent paper on the subject that lists several useful references.  As Suresh mentioned, the recognition problem is co-NP-complete.</p>

<p>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 <i>pure</i> 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."</p>

CC BY-SA 3.0
2011-08-08T09:19:37.543Z
Thank you, this is exactly what I was looking for. Searching for "well-covered graphs" I found many more references.
László Kozma
CC BY-SA 3.0
2011-08-07T22:49:39.727Z
2011-08-07T22:49:39.727Z
Timothy Chow
<p>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?</p>

<p>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?</p>

CC BY-SA 3.0
2011-08-07T02:32:05.310Z
There's a related paper here (http://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
<graph-theory><co.combinatorics>
Maximal/maximum independent sets
László Kozma
# Maximal/maximum independent sets

(Asked by: username_0 on 2011-08-06)

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?

**Tags:** graph-theory, co.combinatorics

> **Comments:**
> **username_1**: There's a related paper here (http://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  

---

## 2 answers

### Answer by username_4 on 2011-08-07. Score: 27 | Accepted answer

Such graphs are called *well-covered* graphs. [Here](http://arxiv.org/abs/1104.4556) 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."

> **Comments:**
> **username_0**: Thank you, this is exactly what I was looking for. Searching for "well-covered graphs" I found many more references.  

---

### Answer by username_2 on 2013-01-01. Score: 9

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.

> **Comments:**
> **username_3**: "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.  

---

