A well-covered graph is a graph for which every minimal vertex cover has the same size, which is equivalent to every maximal
independent vertex set being the same size. It is also equivalent to every maximal independent vertex set being
a maximum independent vertex set
or, in other words, the sets of maximal and maximum independent vertex sets being
equal. Finally, being well-covered is equivalent to equality of the lower
independence number and (upper) independence
number.

Families of well-covered graphs include

1. Andásfai graphs,

2. barbell graphs,

3. centipede graphs,

4. cocktail party graphs,

5. complete graphs ,

6. complete bipartite graphs .

7. cycle complement graphs ,

8. ladder rung graphs ,

9. path complement graphs ,

10. rook graphs ,

11. sunlet graphs,

12. trinagular graphs,

12. triangular honeycomb rook graphs.

It is often easy identify graphs that are not well-covered by simply finding two maximal independent vertex sets of different lengths. Proving that a graph *is*
well-covered appears to be more difficult.

The numbers of well-covered graphs on , 2, ... nodes are 1, 2, 3, 7, 14, 46, 164, 996, 10195, 208168,
... (OEIS A222626), the first few of which
are illustrated above.

The numbers of connected well-covered graphs on , 2, ... nodes are 1, 1, 1, 3, 6, 27, 108, 788, 9035, 196928,
... (OEIS A222625), the first few of which
are illustrated above.

## See also

Lower Independence Number,

Maximal Independent Vertex Set,

Maximum Independent Vertex Set
## Explore with Wolfram|Alpha

## References

Plummer, M. D. "Some Covering Concepts in Graphs." *J. Combin. Th.* **8**, 91-98, 1970.Sloane, N. J. A.
Sequences A222625 and A222626
in "The On-Line Encyclopedia of Integer Sequences."
## Cite this as:

Weisstein, Eric W. "Well-Covered Graph."
From *MathWorld*--A Wolfram Web Resource. https://mathworld.wolfram.com/Well-CoveredGraph.html