TOPICS
Search

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

1. Andásfai graphs,

2. barbell graphs,

3. centipede graphs,

4. cocktail party graphs,

5. complete graphs K_n,

6. complete bipartite graphs K_(n,n).

7. cycle complement graphs C^__n,

8. ladder rung graphs nP_2,

9. path complement graphs P^__n,

10. rook graphs K_m square K_n,

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.

WellCoveredGraph

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

WellCoveredConnectedGraph

The numbers of connected well-covered graphs on n=1, 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