Let be a collection of subsets of a finite set . A subset of that meets every member of is called the vertex cover, or hitting set.
A vertex cover of a graph can also more simply be thought of as a set of vertices of such that every edge of has at least one of member of as an endpoint. The vertex set of a graph is therefore always a vertex cover. The smallest possible vertex cover for a given graph is known as a minimum vertex cover (Skiena 1990, p. 218), and its size is called the vertex cover number, denoted . 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 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.
graph family | OEIS | number of vertex covers |
antiprism graph for | A000000 | X, X, 10, 21, 46, 98, 211, 453, 973, 2090, ... |
bishop graph | A201862 | X, 9, 70, 729, 9918, 167281, ... |
black bishop graph | A000000 | X, X, X, 27, 114, 409, 2066, ... |
-folded cube graph | A000000 | X, 3, 5, 31, 393, ... |
grid graph for | A006506 | X, 7, 63, 1234, 55447, 5598861, ... |
grid graph for | A000000 | X, 35, 70633, ... |
-halved cube graph | A000000 | 2, 3, 5, 13, 57, ... |
-Hanoi graph | A000000 | 4, 52, 108144, ... |
hypercube graph | A027624 | 3, 7, 35, 743, 254475, 19768832143, ... |
king graph | A063443 | X, 5, 35, 314, 6427, ... |
knight graph | A141243 | X, 16, 94, 1365, 55213, ... |
-Möbius ladder | A182143 | X, X, 15, 33, 83, 197, 479, 1153, 2787, ... |
-Mycielski graph | A000000 | 2, 3, 11, 103, 7407, ... |
odd graph | A000000 | 2, 4, 76, ... |
prism graph for | A051927 | X, X, 13, 35, 81, 199, 477, 1155, 2785, ... |
queen graph | A000000 | 2, 5, 18, 87, 462, ... |
rook graph | A002720 | 2, 7, 34, 209, 1546, 13327, 130922, ... |
-Sierpiński gasket graph | A000000 | 4, 14, 440, ... |
-triangular graph | A000000 | X, 2, 4, 10, 26, 76, 232, 764, ... |
-web graph for | A000000 | X, X, 68, 304, 1232, 5168, 21408, ... |
white bishop graph | A000000 | X, X, X, 27, 87, 409, 1657, ... |
Many families of graphs have simple closed forms for counts of vertex covers, as summarized in the following table. Here, is a Fibonacci number, is a Lucas number, is a Laguerre polynomial, is the golden ratio, and , , are the roots of .