Well-covered graph
Encyclopedia
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. Well-covered graphs were defined and first studied by .
An independent set
in a graph is a set of vertices no two of which are adjacent to each other. If is a vertex cover in a graph , the complement
of must be an independent set, and vice versa. is a minimal vertex cover if and only if its complement is a maximal independent set, and 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 apply only 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 , deleting from the graph produces a graph with a smaller minimum dominating set
.
The independence complex
of a graph is the simplicial complex
having a simplex for each independent set in . 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.
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. 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 is either a polygon or a set of points, is the set of open line segments that have vertices of as endpoints and are otherwise disjoint from , and is the intersection graph
of (a graph that has a vertex for each line segment in and an edge for each two line segments that cross each other), then is well-covered. For in this case, every maximal independent set in corresponds to the set of edges in a triangulation of , and a calculation involving the Euler characteristic
shows that every two triangulations have the same number of edges as each other.
If is any -vertex graph, then the rooted product of with a one-edge graph (that is, the graph formed by adding new vertices to , each of degree one and each adjacent to a distinct vertex in ) is well-covered. For, a maximal independent set in must consist of an arbitrary independent set in together with the degree-one neighbors of the complementary set, and must therefore have size . More generally, given any graph together with a clique cover (a partition of the vertices of into cliques), the graph formed by adding an additional vertex to each clique is well-covered; the rooted product is the special case of this construction when consists of one-vertex cliques. Thus, every graph is an induced subgraph of a well-covered graph.
A bipartite graph is well-covered if and only if it has a perfect matching with the property that, for every edge in , the induced subgraph of the neighbors of and forms a complete bipartite graph
. The characterization in terms of matchings can be extended from bipartite graphs to very well covered graphs: a graph is very well covered if and only if it has a perfect matching with the following two properties:
Moreover, if is very well covered, then every perfect matching in satisfies these properties.
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 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. 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 , the subgraph of vertices within distance three of 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. A closely related but more complex characterization applies to well-covered graphs of girth five or more.
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.
The seven 3-connected cubic well-covered graphs are the complete graph
, the graphs of the triangular prism
and the pentagonal prism
, the Dürer graph
, the utility graph , an eight-vertex graph obtained from the utility graph by a Y-Δ transform, and the 14-vertex generalized Petersen graph
. Of these graphs, the first four are planar graph
s and therefore also the only four cubic polyhedral graph
s (graphs of simple
convex polyhedra) that are well-covered. Four of the graphs (the two prisms, the Dürer graph, and ) 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 labels , , and . Fragments or may be used to replace the nodes of a cycle or the interior nodes of a path, while fragment is used to replace the two end nodes of a path. Fragment contains a bridge
, so the result of performing this replacement process on a path and using fragment 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.
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 and , with at least two of the fragments being of type ; a graph of this type is planar if and only if it does not contain any fragments of type . The other family is formed by replacing the nodes of a path by fragments of type and ; all such graphs are planar.
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. 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. For instance, a well-covered 3-connected maximal planar graph may be obtained via the clique cover construction from any -vertex maximal planar graph in which there are disjoint triangle faces by adding new vertices, one within each of these faces.
; that is, complementarily, testing whether a graph is well-covered is coNP-complete. 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.
In contrast, it is possible to test whether a given graph is very well covered in polynomial time. To do so, find the subgraph of 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 has a perfect matching. 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.
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.
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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a well-covered graph is an undirected graph in which every minimal vertex cover
Vertex cover
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
has the same size as every other minimal vertex cover. Well-covered graphs were defined and first studied by .
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, 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
Independent set
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
in a graph is a set of vertices no two of which are adjacent to each other. If is a vertex cover in a graph , the complement
Complement (set theory)
In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...
of must be an independent set, and vice versa. is a minimal vertex cover if and only if its complement is a maximal independent set, and 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 apply only to connected graphs
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
, 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
Critical graph
In general the notion of criticality can refer to any measure.But in graph theory, when the term is used without any qualification, it almost always refers to the chromatic number of a graph....
for vertex covering in the sense that, for every vertex , deleting from the graph produces a graph with a smaller minimum dominating set
Dominating set
In graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge...
.
The independence complex
Clique complex
Clique complexes, flag complexes, and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.-Clique complex:...
of a graph is the simplicial complex
Simplicial complex
In mathematics, a simplicial complex is a topological space of a certain kind, constructed by "gluing together" points, line segments, triangles, and their n-dimensional counterparts...
having a simplex for each independent set in . 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 graphCycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
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
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
is well-covered: every maximal independent set consists of a single vertex. A complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
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
Rook's graph
In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard: each vertex represents a square on a chessboard and each edge represents a legal move...
is well covered: if one places any set of rooks
Rook (chess)
A rook is a piece in the strategy board game of chess. Formerly the piece was called the castle, tower, marquess, rector, and comes...
on a chessboard
Chessboard
A chessboard is the type of checkerboard used in the board game chess, and consists of 64 squares arranged in two alternating colors...
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 is either a polygon or a set of points, is the set of open line segments that have vertices of as endpoints and are otherwise disjoint from , and is the intersection graph
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
of (a graph that has a vertex for each line segment in and an edge for each two line segments that cross each other), then is well-covered. For in this case, every maximal independent set in corresponds to the set of edges in a triangulation of , and a calculation involving the Euler characteristic
Euler characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent...
shows that every two triangulations have the same number of edges as each other.
If is any -vertex graph, then the rooted product of with a one-edge graph (that is, the graph formed by adding new vertices to , each of degree one and each adjacent to a distinct vertex in ) is well-covered. For, a maximal independent set in must consist of an arbitrary independent set in together with the degree-one neighbors of the complementary set, and must therefore have size . More generally, given any graph together with a clique cover (a partition of the vertices of into cliques), the graph formed by adding an additional vertex to each clique is well-covered; the rooted product is the special case of this construction when consists of one-vertex cliques. Thus, every graph is an induced subgraph of a well-covered graph.
Bipartiteness, very well covered graphs, and girth
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 dominating set) contains exactly half of the vertices. This definition includes the rooted products of a graph and a one-edge graph. It also includes, for instance, the bipartite well-covered graphs studied by and : in bipartite graph without isolated vertices, both sides of any bipartition form maximal independent sets (and minimal dominating sets), so if the graph is well-covered both sides must have equally many vertices. In a well-covered graph with vertices, the size of a maximum independent set is at most , so very well covered graphs are the well covered graphs in which the maximum independent set size is as large as possible.A bipartite graph is well-covered if and only if it has a perfect matching with the property that, for every edge in , the induced subgraph of the neighbors of and forms a complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
. The characterization in terms of matchings can be extended from bipartite graphs to very well covered graphs: a graph is very well covered if and only if it has a perfect matching with the following two properties:
- No edge of belongs to a triangle in , and
- If an edge of is the central edge of a three-edge path in , then the two endpoints of the path must be adjacent.
Moreover, if is very well covered, then every perfect matching in satisfies these properties.
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 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. 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 , the subgraph of vertices within distance three of is acyclic) then it is well-covered if and only if every vertex of degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
greater than one has exactly one neighbor of degree one. A closely related but more complex characterization applies to well-covered graphs of girth five or more.
Regularity and planarity
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
(3-regular
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
) well-covered graphs have been classified: they consist of seven 3-connected
K-vertex-connected graph
In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...
examples, together with three infinite families of cubic graphs with lesser connectivity.
The seven 3-connected cubic well-covered graphs are the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
, the graphs of the triangular prism
Triangular prism
In geometry, a triangular prism is a three-sided prism; it is a polyhedron made of a triangular base, a translated copy, and 3 faces joining corresponding sides....
and the pentagonal prism
Pentagonal prism
In geometry, the pentagonal prism is a prism with a pentagonal base. It is a type of heptahedron with 7 faces, 15 edges, and 10 vertices.- As a semiregular polyhedron :...
, the Dürer graph
Dürer graph
In the mathematical field of graph theory, the Dürer graph is an undirected graph with 12 vertices and 18 edges. It is named after Albrecht Dürer, whose 1514 engraving Melencolia I includes a depiction of Dürer's solid, a convex polyhedron having the Dürer graph as its skeleton...
, the utility graph , an eight-vertex graph obtained from the utility graph by a Y-Δ transform, and the 14-vertex generalized Petersen graph
Generalized Petersen graph
In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized...
. Of these graphs, the first four are planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s and therefore also the only four cubic polyhedral graph
Polyhedral graph
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
s (graphs of simple
Simple polytope
In geometry, a d-dimensional simple polytope is a d-dimensional polytope each of whose vertices are adjacent to exactly d edges . The vertex figure of a simple d-polytope is a -simplex....
convex polyhedra) that are well-covered. Four of the graphs (the two prisms, the Dürer graph, and ) 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 labels , , and . Fragments or may be used to replace the nodes of a cycle or the interior nodes of a path, while fragment is used to replace the two end nodes of a path. Fragment contains a bridge
Bridge (graph theory)
In graph theory, a bridge is an edge whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle....
, so the result of performing this replacement process on a path and using fragment 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.
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 and , with at least two of the fragments being of type ; a graph of this type is planar if and only if it does not contain any fragments of type . The other family is formed by replacing the nodes of a path by fragments of type and ; all such graphs are planar.
Complementing the characterization of well-covered simple polyhedra in three dimensions, researchers have also considered the well-covered simplicial polyhedra
Simplicial polytope
In geometry, a simplicial polytope is a d-polytope whose facets are all simplices.For example, a simplicial polyhedron contains only triangular faces and corresponds via Steinitz's theorem to a maximal planar graph....
, or equivalently the well-covered maximal planar graphs. Every maximal planar graph with five or more vertices has vertex connectivity 3, 4, or 5. 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
Pentagonal dipyramid
In geometry, the pentagonal bipyramid is third of the infinite set of face-transitive bipyramids.Each bipyramid is the dual of a uniform prism.If the faces are equilateral triangles, it is a deltahedron and a Johnson solid...
, the snub disphenoid
Snub disphenoid
In geometry, the snub disphenoid is one of the Johnson solids . It is a three-dimensional solid that has only equilateral triangles as faces, and is therefore a deltahedron. It is not a regular polyhedron because some vertices have four faces and others have five...
, and an irregular polyhedron (a nonconvex deltahedron
Deltahedron
A deltahedron is a polyhedron whose faces are all equilateral triangles. The name is taken from the Greek majuscule delta , which has the shape of an equilateral triangle. There are infinitely many deltahedra, but of these only eight are convex, having 4, 6, 8, 10, 12, 14, 16 and 20 faces...
) with 12 vertices, 30 edges, and 20 triangular faces. However, there are infinitely many 3-connected well-covered maximal planar graphs. For instance, a well-covered 3-connected maximal planar graph may be obtained via the clique cover construction from any -vertex maximal planar graph in which there are disjoint triangle faces by adding new vertices, one within each of these faces.
Complexity
Testing whether a graph contains two maximal independent sets of different sizes is NP-completeNP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
; that is, complementarily, testing whether a graph is well-covered is coNP-complete. 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.
In contrast, it is possible to test whether a given graph is very well covered in polynomial time. To do so, find the subgraph of 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 has a perfect matching. 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.
A graph is said to be equimatchable if every maximal matching is maximum; that is, it is equimatchable if its line graph
Line graph
In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...
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.
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.