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  is known as the vertex cover number and is denoted .

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.

---

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength