Well-covered graph

In the original paper defining well-covered graphs, Plummer writes that this is "obviously equivalent" to the property that every two minimal covers have the same number of vertices as each other.

If C is a vertex cover in a graph G, the complement of C must be an independent set, and vice versa.

[5] A cycle graph of length four or five is well-covered: in each case, every maximal independent set has size two.

[6] Every complete graph is well-covered: every maximal independent set consists of a single vertex.

The complement graph of a triangle-free graph with no isolated vertices is well-covered: it has no independent sets larger than two, and every single vertex can be extended to a two-vertex independent set.

[8] The graph whose vertices are the diagonals of a simple polygon and whose edges connect pairs of diagonals that cross each other is well-covered, because its maximal independent sets are triangulations of the polygon and all triangulations have the same number of edges.

Favaron (1982) defines a very well covered graph to be a well-covered graph (possibly disconnected, but with no isolated vertices) in which each maximal independent set (and therefore also each minimal vertex cover) contains exactly half of the vertices.

It also includes, for instance, the bipartite well-covered graphs studied by Ravindra (1977) and Berge (1981): in a bipartite graph without isolated vertices, both sides of any bipartition form maximal independent sets (and minimal vertex covers), so if the graph is well-covered both sides must have equally many vertices.

[15] A closely related but more complex characterization applies to well-covered graphs of girth five or more.

The other family is formed by replacing the nodes of a path by fragments of type B and C; all such graphs are planar.

Therefore, the clique cover construction, which for these graphs consists of subdividing each of these t triangles into three new triangles meeting at a central vertex, produces a well-covered maximal planar graph.

[23] Although it is easy to find maximum independent sets in graphs that are known to be well-covered, it is also NP-hard for an algorithm to produce as output, on all graphs, either a maximum independent set or a guarantee that the input is not well-covered.

[24] In contrast, it is possible to test whether a given graph G is very well covered in polynomial time.

A well-covered graph, the intersection graph of the nine diagonals of a hexagon . The three red vertices form one of its 14 equal-sized maximal independent sets, and the six blue vertices form the complementary minimal vertex cover.
The seven cubic 3-connected well-covered graphs
A cubic 1-connected well-covered graph, formed by replacing each node of a six-node path by one of three fragments
The snub disphenoid , one of four well-covered 4-connected 3-dimensional simplicial polyhedra.