Well-covered graph

In graph theory, a well-covered graph is a kind of undirected graph. In these graphs, every minimal vertex cover has the same size. A vertex cover is a set of vertices (points) that touches all the edges (lines) in the graph. A cover is minimal if taking away any vertex means some edge is not covered anymore. 

We can also describe well-covered graphs in another way. They are graphs where every maximal independent set has the same size. Michael D. Plummer first defined and studied well-covered graphs in 1970.

There are many kinds of well-covered graphs. These include complete graphs and balanced complete bipartite graphs. Another example is the rook's graph. In a rook's graph, vertices represent squares on a chessboard. Edges represent the moves of a chess rook. Mathematicians know how to find well-covered cubic graphs and well-covered claw-free graphs. They can also find well-covered graphs with high girth. Computers can find these graphs in polynomial time (quickly). But for other kinds of graphs, it is very hard to test if they are well-covered. This is a coNP-complete problem.

Definitions
A vertex cover in an undirected graph is a group of vertices. This group touches every edge in the graph. A vertex cover is minimal if we cannot remove any vertex from it. If we remove a vertex, the edges are not all covered. A vertex cover is minimum if there is no other cover with fewer vertices. A well-covered graph is a graph where every minimal cover is also a minimum cover. In the first paper about these graphs, Plummer wrote that this is the same as saying every minimal cover has the same number of vertices.. Plummer uses "point" to mean a vertex in a graph, "line" to mean an edge, and "point cover" to mean a vertex cover; people do not use these words this way anymore.

An independent set in a graph is a group of vertices. No two vertices in this group are connected to each other. Let  be a vertex cover in a graph . The complement of  (the vertices not in ) must be an independent set. The opposite is also true.  is a minimal vertex cover if its complement  is a maximal independent set.  is a minimum vertex cover if its complement is a maximum independent set. Because of this, a well-covered graph is also a graph where every maximal independent set has the same size. Or, we can say it is a graph where every maximal independent set is a maximum independent set.

The first paper about well-covered graphs only talked about connected graphs. But these definitions work for disconnected graphs too. Later, some writers used a different rule. They said a well-covered graph must not have any isolated vertices (vertices with no edges). 

Connected well-covered graphs do not have essential vertices. An essential vertex is a vertex that is in every minimum vertex cover. Also, every well-covered graph is a critical graph for vertex covering. This means if we delete any vertex , the new graph has a smaller minimum vertex cover.

The independence complex of a graph  is a simplicial complex. It has a simplex for each independent set in . A simplicial complex is pure if all its biggest simplices have the same cardinality (size). So, a well-covered graph is a graph with a pure independence complex.For examples of papers using these words, see  and .

Examples

A cycle graph with four or five vertices is well-covered. In both graphs, every maximal independent set has size two. A cycle with seven vertices is also well-covered. A path with three edges is well-covered too. 

Every complete graph is well-covered. In a complete graph, every maximal independent set has only one vertex. Every cluster graph is also well-covered. A cluster graph is made of separate complete graphs. 

A complete bipartite graph is well-covered if both sides have the same number of vertices. These two sides are the only two maximal independent sets. The complement graph of a triangle-free graph is well-covered if it has no isolated vertices. In this graph, no independent set is larger than two. Also, every single vertex can be part of a two-vertex independent set.

A rook's graph is well-covered. Imagine placing rooks on a chessboard so they do not attack each other. We can always keep adding rooks until there is one on every row and column.The rook's graphs are the line graphs of complete bipartite graphs. So, saying rook's graphs are well-covered is the same as saying complete bipartite graphs are equimatchable. See  and . 

Imagine a graph where the vertices are the diagonals of a simple polygon. The edges connect diagonals that cross each other. This graph is well-covered. Its maximal independent sets are triangulations of the polygon. All triangulations have the same number of edges.

Let  be a graph with  vertices. We can make a new graph called the rooted product of  with a one-edge graph. To do this, we add  new vertices to . Each new vertex connects to one vertex in . This new graph is well-covered. A maximal independent set in the new graph must have size .This example was studied by . They are also exactly the graphs where the domination number is . Theorem 4.4 of  also talks about this property. 

There is a more general rule. Take any graph  and a clique cover (a way to split the vertices into groups called cliques). We can add a new vertex to each clique. This makes a graph . This new graph is well-covered. The rooted product is a special case of this. In that case, each clique has only one vertex.For the clique cover construction, see , Lemma 3.2. This source talks about the purity of the independence complex. Because of this, every graph is an induced subgraph of a well-covered graph.

Bipartiteness, very well covered graphs, and girth
 writes about a very well covered graph. This is a well-covered graph that has no isolated vertices. Also, every maximal independent set must have exactly half of the vertices. This means every minimal vertex cover also has half of the vertices. The rooted products of a graph  and a one-edge graph are very well covered. 

Bipartite well-covered graphs are also very well covered. These were studied by  and . In a bipartite graph, the vertices are in two groups. If there are no isolated vertices, each group is a maximal independent set. If the graph is well-covered, both groups must have the same number of vertices. In a well-covered graph with  vertices, the largest independent set has at most  vertices. So, very well covered graphs are the well covered graphs with the biggest possible independent sets.

A bipartite graph  is well-covered if it has a perfect matching  with a special property. For every edge  in , look at the neighbors of  and . The induced subgraph of these neighbors must be a complete bipartite graph.; . 

We can use matchings to describe very well covered graphs too. A graph  is very well covered if it has a perfect matching  that follows two rules:
 No edge in  is part of a triangle in .
 If an edge in  is the middle of a path with three edges, the ends of the path must be connected.
If  is very well covered, every perfect matching follows these rules.; ; .

Trees are a type of bipartite graph. It is easy to test if a tree is well-covered. If  is a tree with more than two vertices, it is well-covered if every non-leaf node connects to exactly one leaf. 

This rule also works for graphs that look like trees locally. If a graph has girth eight or more, it is well-covered if every vertex with degree more than one has exactly one neighbor with degree one.; , Theorem 4.1. There is a similar rule for well-covered graphs with girth five or more.; , Theorem 4.2.

Regularity and planarity
Mathematicians have listed all the cubic (3-regular) well-covered graphs. There are seven 3-connected examples. There are also three infinite families of cubic graphs that are less connected.

The seven 3-connected cubic well-covered graphs are:
 The complete graph .
 The graph of the triangular prism.
 The graph of the pentagonal prism.
 The Dürer graph.
 The utility graph .
 An eight-vertex graph made from the utility graph by a Y-Δ transform.
 The 14-vertex generalized Petersen graph .; ; ; . 

The first four of these are planar graphs. They are the only four cubic polyhedral graphs that are well-covered. Four of these graphs are generalized Petersen graphs.

The other cubic well-covered graphs are made by replacing nodes in a path or cycle. We replace them with shapes called fragments.  calls these fragments , , and . 
 Fragment  has a bridge. Using fragment  makes the graph 1-vertex-connected. All these graphs are planar.; ; .
 There are two types of 2-vertex-connected graphs. One type uses fragments  and  on a cycle. The other uses fragments  and  on a path. All graphs in the second type are planar.

Researchers have also looked at well-covered simplicial polyhedra. These are the same as well-covered maximal planar graphs. Every maximal planar graph with five or more vertices has vertex connectivity 3, 4, or 5.The complete graphs on 1, 2, 3, and 4 vertices are all maximal planar and well-covered. 
 There are no well-covered 5-connected maximal planar graphs.
 There are only four 4-connected ones: the regular octahedron, the pentagonal dipyramid, the snub disphenoid, and an irregular polyhedron with 12 vertices.
 There are infinitely many 3-connected ones.. 

For example, take a maximal planar graph with  separate triangle faces. We can divide each of these triangles into three new triangles. This makes a well-covered maximal planar graph.These graphs are called the -family by .

Complexity
It is hard to check if a graph is well-covered. It is a coNP-complete problem.; ; . This means it is NP-complete to check if a graph has two maximal independent sets of different sizes. It is easy to find maximum independent sets in well-covered graphs. But it is NP-hard to find a maximum independent set if we do not know the graph is well-covered..

However, we can test if a graph  is very well covered in polynomial time (quickly). First, we find the edges that follow the rules for a very well covered graph. Then we check if these edges form a perfect matching. Some problems that are usually very hard, like finding a Hamiltonian cycle, are easy for very well covered graphs..

A graph is equimatchable if every maximal matching is a maximum matching. This is the same as saying its line graph is well-covered. A graph is randomly matchable if every maximal matching is a perfect matching. The only connected graphs like this are complete graphs and balanced complete bipartite graphs. We can test if a line graph or a claw-free graph is well-covered in polynomial time.; ; .

We can also quickly recognize well-covered graphs with girth five or more. The same is true for 3-regular well-covered graphs.; .

Notes

References

.
. As cited by .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
. As cited by .
.
.
.

Category:Graph families