Well-covered graph

In graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970. The well-covered graphs include all complete graphs, balanced complete bipartite graphs, and the rook's graphs whose vertices represent squares of a chessboard and edges represent moves of a chess rook. Known characterizations of the well-covered cubic graphs, well-covered claw-free graphs, and well-covered graphs of high girth allow these graphs to be recognized in polynomial time, but testing whether other kinds of graph are well-covered is a coNP-complete problem. A vertex cover in a graph is a set of vertices that touches every edge in the graph. A vertex cover is minimal, or irredundant, if removing any vertex from it would destroy the covering property. It is minimum if there is no other vertex cover with fewer vertices. A well-covered graph is one in which every minimal cover is also minimum. 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. An independent set in a graph is a set of vertices no two of which are adjacent to each other. If C is a vertex cover in a graph G, the complement of C must be an independent set, and vice versa. C is a minimal vertex cover if and only if its complement I is a maximal independent set, and C is a minimum vertex cover if and only if its complement is a maximum independent set. Therefore, a well-covered graph is, equivalently, a graph in which every maximal independent set has the same size, or a graph in which every maximal independent set is maximum. In the original paper defining well-covered graphs, these definitions were restricted to connected graphs, although they are meaningful for disconnected graphs as well.