Vertex Cover

Let S be a collection of subsets of a finite set X. A subset Y of X that meets every member of S is called the vertex cover, or hitting set.

A vertex cover of a graph G can also more simply be thought of as a set S of vertices of G such that every edge of G has at least one of member of S as an endpoint. The vertex set of a graph is therefore always a vertex cover. The smallest possible vertex cover for a given graph G is known as a minimum vertex cover (Skiena 1990, p. 218), and its size is called the vertex cover number, denoted tau(G). Vertex covers, indicated with red coloring, are shown above for a number of graphs. In a complete k-partite graph, and vertex cover contains vertices from at least k-1 stages.

A set of vertices is a vertex cover iff its complement forms an independent vertex set (Skiena 1990, p. 218). The counts of vertex covers and independent vertex sets in a graph are therefore the same.

A vertex cover having the smallest possible number of vertices for a given graph is known as a minimum vertex cover. A minimum vertex cover of a graph can be found in the Wolfram Language using FindVertexCover [g].

A graph can be tested in the Wolfram Language to see if it is a vertex cover of a given graph using VertexCoverQ [g]. Precomputed vertex covers for many named graphs can be looked up using GraphData [graph, "VertexCovers"].

Vertex cover counts for some families of graphs are summarized in the following table.

Many families of graphs have simple closed forms for counts of vertex covers, as summarized in the following table. Here, F_n is a Fibonacci number, L_n is a Lucas number, L_n(x) is a Laguerre polynomial, phi is the golden ratio, and alpha, beta, gamma are the roots of x^3-x^2-2x-1.

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Vertex Cover." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/VertexCover.html

Subject classifications