Well-covered graph

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.

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. Equivelently, these are the graphs in which every maximal independent set has the same size. Well-covered graphs were defined and first studied by Plummer (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 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 (1970) 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.^[1]

In the original paper defining well-covered graphs, these definitions were restricted to connected graphs,^[2] 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.^[3] 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.^[2] 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.^[2]

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.^[4]

Examples

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

A non-attacking placement of eight rooks on a chessboard. If fewer than eight rooks are placed in a non-attacking way on a chessboard, they can always be extended to eight rooks that remain non-attacking.

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

If P is either a polygon or a set of points, S is the set of open line segments that have vertices of P as endpoints and are otherwise disjoint from P, and G is the intersection graph of S (a graph that has a vertex for each line segment in S and an edge for each two line segments that cross each other), then G is well-covered. For in this case, every maximal independent set in G corresponds to the set of edges in a triangulation of P, and a calculation involving the Euler characteristic shows that every two triangulations have the same number of edges as each other.^[5]

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.^[6] More generally, given any graph G together with a clique cover (a partition p of the vertices of G into cliques), the graph G^p 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.^[7] Thus, every graph is an induced subgraph of a well-covered graph.

Bipartiteness, very well covered graphs, and girth

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. This definition includes the rooted products of a graph G and a one-edge graph. It also includes, for instance, the bipartite well-covered graphs studied by Ravindra (1977) and Berge (1981): in 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. In a well-covered graph with n vertices, the size of a maximum independent set is at most n/2, so very well covered graphs are the well covered graphs in which the maximum independent set size is as large as possible.^[8]

A bipartite graph G is well-covered if and only if it has a perfect matching M with the property that, for every edge uv in M, the induced subgraph of the neighbors of u and v forms a complete bipartite graph.^[9] The characterization in terms of matchings can be extended from bipartite graphs to very well covered graphs: a graph G is very well covered if and only if it has a perfect matching M with the following two properties:

1. No edge of M belongs to a triangle in G, and
2. If an edge of M is the central edge of a three-edge path in G, then the two endpoints of the path must be adjacent.

Moreover, if G is very well covered, then every perfect matching in G satisfies these properties.^[10]

Trees are a special case of bipartite graphs, and testing whether a tree is well-covered can be handled as a much simpler special case of the characterization of well-covered bipartite graphs: if G is a tree with more than two vertices, it is well-covered if and only if each non-leaf node of the tree is adjacent to exactly one leaf.^[9] The same characterization applies to graphs that are locally tree-like, in the sense that low-diameter neighborhoods of every vertex are acyclic: if a graph has girth eight or more (so that, for every vertex v, the subgraph of vertices within distance three of v is acyclic) then it is well-covered if and only if every vertex of degree greater than one has exactly one neighbor of degree one.^[11] A closely related but more complex characterization applies to well-covered graphs of girth five or more.^[12]

Regularity and planarity

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.

The cubic (3-regular) well-covered graphs have been classified: they consist of seven 3-connected examples, together with three infinite families of cubic graphs with lesser connectivity.^[13]

The seven 3-connected cubic well-covered graphs are the complete graph K₄, the graphs of the triangular prism and the pentagonal prism, the Dürer graph, the utility graph K_3,3, an eight-vertex graph obtained from the utility graph by a Y-Δ transform, and the 14-vertex generalized Petersen graph G(7,2).^[14] Of these graphs, the first four are planar graphs. They are the only four cubic polyhedral graphs (graphs of simple convex polyhedra) that are well-covered. Four of the graphs (the two prisms, the Dürer graph, and G(7,2)) are generalized Petersen graphs.

The 1- and 2-connected cubic well-covered graphs are all formed by replacing the nodes of a path or cycle by three fragments of graphs which Plummer (1993) labels A, B, and C. Fragments A or B may be used to replace the nodes of a cycle or the interior nodes of a path, while fragment C is used to replace the two end nodes of a path. Fragment A contains a bridge, so the result of performing this replacement process on a path and using fragment A to replace some of the path nodes (and the other two fragments for the remaining nodes) is a 1-vertex-connected cubic well-covered graph. All 1-vertex-connected cubic well-covered graphs have this form, and all such graphs are planar.^[13]

There are two types of 2-vertex-connected cubic well-covered graphs. One of these two families is formed by replacing the nodes of a cycle by fragments A and B, with at least two of the fragments being of type A; a graph of this type is planar if and only if it does not contain any fragments of type B. The other family is formed by replacing the nodes of a path by fragments of type B and C; all such graphs are planar.^[13]

Complementing the characterization of well-covered simple polyhedra in three dimensions, researchers have also considered the well-covered simplicial polyhedra, or equivalently the well-covered maximal planar graphs. Every maximal planar graph with five or more vertices has vertex connectivity 3, 4, or 5.^[15] There are no well-covered 5-connected maximal planar graphs, and there are only four 4-connected well-covered maximal planar graphs: the graphs of the regular octahedron, the pentagonal dipyramid, the snub disphenoid, and an irregular polyhedron (a nonconvex deltahedron) with 12 vertices, 30 edges, and 20 triangular faces. However, there are infinitely many 3-connected well-covered maximal planar graphs.^[16] For instance, a well-covered 3-connected maximal planar graph may be obtained via the clique cover construction^[7] from any 3t-vertex maximal planar graph in which there are t disjoint triangle faces by adding t new vertices, one within each of these faces.

Complexity

Testing whether a graph contains two maximal independent sets of different sizes is NP-complete; that is, complementarily, testing whether a graph is well-covered is coNP-complete.^[17] 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.^[18]

In contrast, it is possible to test whether a given graph G is very well covered in polynomial time. To do so, find the subgraph H of G consisting of the edges that satisfy the two properties of a matched edge in a very well covered graph, and then use a matching algorithm to test whether H has a perfect matching.^[10] Some problems that are NP-complete for arbitrary graphs, such as the problem of finding a Hamiltonian cycle, may also be solved in polynomial time for very well covered graphs.^[19]

A graph is said to be equimatchable if every maximal matching is maximum; that is, it is equimatchable if its line graph is well-covered. It is possible to test whether a line graph, or more generally a claw-free graph, is well-covered in polynomial time.^[20]

The characterizations of well-covered graphs with girth five or more, and of well-covered graphs that are 3-regular, also lead to efficient polynomial time algorithms to recognize these graphs.^[21]

Notes

References