TOPICS

# Well-Covered Graph

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

10. rook graphs ,

11. sunlet 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.

Lower Independence Number, Maximal Independent Vertex Set, Maximum Independent Vertex Set

## Explore with Wolfram|Alpha

More things to try:

## 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