In graph theory, a well-covered graph is an undirected graph in which the minimal vertex covers all have the same size. Here, a vertex cover is a set of vertices that touches all edges, and it is minimal if removing any vertex from it would leave some edge uncovered. Equivalently, well-covered graphs 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.
Definitions A vertex cover in an undirected 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: the removal would cause some edge to become uncovered. 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. Some later authors have replaced the connectivity requirement with the weaker requirement that a well-covered graph must not have any isolated vertices. For both connected well-covered graphs and well-covered graphs without isolated vertices, there can be no essential vertices, vertices which belong to every minimum vertex cover. Additionally, every well-covered graph is a critical graph for vertex covering in the sense that, for every vertex v, deleting v from the graph produces a graph with a smaller minimum vertex cover. The independence complex of a graph G is the simplicial complex having a simplex for each independent set in G. A simplicial complex is said to be pure if all its maximal simplices have the same cardinality, so a well-covered graph is equivalently a graph with a pure independence complex.
Examples
A cycle graph of length four or five is well-covered: in each case, every maximal independent set has size two. A cycle of length seven, and a path of length three, are also well-covered. Every complete graph is well-covered: every maximal independent set consists of a single vertex. Similarly, every cluster graph (a disjoint union of complete graphs) is well-covered. A complete bipartite graph is well-covered if the two sides of its bipartition have equal numbers of vertices, for these are its only two maximal independent sets. 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. A rook's graph is well-covered: if one places any set of rooks on a chessboard so that no two rooks are attacking each other, it is always possible to continue placing more non-attacking rooks until there is one on every row and column of the chessboard. 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. If G is any n-vertex graph, then the rooted product of G with a one-edge graph (that is, the graph H formed by adding n new vertices to G, each of degree one and each adjacent to a distinct vertex in G) is well-covered. For, a maximal independent set in H must consist of an arbitrary independent set in G together with the degree-one neighbors of the complementary set, and must therefore have size n. More generally, given any graph G together with a clique cover (a partition p of the vertices of G into cliques), the graph Gp formed by adding another vertex to each clique is well-covered; the rooted product is the special case of this construction when p consists of n one-vertex cliques. Thus, every graph is an induced subgraph of a well-covered graph.
… excerpt ends here. Continue reading the full article.
