TOPICS
Search

Minimum Vertex Cover


A minimum vertex cover is a vertex cover having the smallest possible number of vertices for a given graph. The size of a minimum vertex cover of a graph G is known as the vertex cover number and is denoted tau(G).

Every minimum vertex cover is a minimal vertex cover (i.e., a vertex cover that is not a proper subset of any other cover), but not necessarily vice versa.

Finding a minimum vertex cover of a general graph is an NP-complete problem. However, for a bipartite graph, the König-Egeváry theorem allows a minimum vertex cover to be found in polynomial time.

A minimum vertex cover of a graph can be computed in the Wolfram Language using FindVertexCover[g]. There is currently no Wolfram Language function to compute all minimum vertex covers.

Minimum vertex covers correspond to the complements of maximum independent vertex sets.


See also

Independence Number, Minimal Vertex Cover, Minimum Edge Cover, Vertex Cover, Vertex Cover Number

Explore with Wolfram|Alpha

References

Pemmaraju, S. and Skiena, S. "Minimum Vertex Cover." §7.5.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 317, 2003.Skiena, S. "Minimum Vertex Cover." §5.6.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 218, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Cite this as:

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

Subject classifications