TOPICS
Search

Vertex Cover

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

VertexCover

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 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 with k nonempty parts, every vertex cover contains all the vertices of at least k-1 parts.

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 minimum vertex cover of a graph can be found in the Wolfram Language using FindVertexCover[g].

A list of vertices can be tested in the Wolfram Language to see if it is a vertex cover of a graph using VertexCoverQ[g, vlist]. 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. The index of each value list in the table starts at 1. An X indicates a parameter value excluded by the family conventions used in that row.

graph familyOEISnumber of vertex covers
antiprism graph for n>=3X, X, 10, 21, 46, 98, 211, 453, 973, 2090, ...
n×n bishop graphA2018622, 9, 70, 729, 9918, 167281, ...
n×n black bishop graph2, 3, 10, 27, 114, 409, 2066, ...
n-folded cube graphX, 3, 5, 31, 393, ...
grid graph P_n square P_n for n>=2A006506X, 7, 63, 1234, 55447, 5598861, ...
grid graph P_n square P_n square P_n for n>=2X, 35, 70633, ...
n-halved cube graph2, 3, 5, 13, 57, ...
n-Hanoi graph4, 52, 108144, ...
hypercube graph Q_nA0276243, 7, 35, 743, 254475, 19768832143, ...
n×n king graphA0634432, 5, 35, 314, 6427, ...
n×n knight graphA1412432, 16, 94, 1365, 55213, ...
n-Möbius ladderA182143X, X, 15, 33, 83, 197, 479, 1153, 2787, ...
n-Mycielski graph2, 3, 11, 103, 7407, ...
odd graph O_n2, 4, 76, ...
prism graph Y_n for n>=3A051927X, X, 13, 35, 81, 199, 477, 1155, 2785, ...
n×n queen graph2, 5, 18, 87, 462, ...
n×n rook graphA0027202, 7, 34, 209, 1546, 13327, 130922, ...
n-Sierpiński gasket graph4, 14, 440, ...
n-triangular graphX, 2, 4, 10, 26, 76, 232, 764, ...
n-web graph for n>=3X, X, 68, 304, 1232, 5168, 21408, ...
n×n white bishop graphX, 3, 7, 27, 87, 409, 1657, ...

Many families of graphs have simple closed forms for counts of vertex covers, as summarized in the following table. Here n is a positive integer. The formulas for the antiprism graph, cycle graph, gear graph, helm graph, Möbius ladder, pan graph, prism graph, sun graph, and sunlet graph assume n>=3. The formula for the wheel graph assumes n>=4, and that for the 2n-crossed prism graph assumes n>=2. 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.

graph familynumber of vertex covers
Andrásfai graph2^(n-1)(3n-1)+1
antiprism graphalpha^n+beta^n+gamma^n
book graph S_(n+1) square P_23^n+2^(n+1)
cocktail party graph3n+1
complete bipartite graph K_(n,n)2^(n+1)-1
complete graph K_nn+1
complete tripartite graph K_(n,n,n)3·2^n-2
2n-crossed prism graph2^(-n)[(7-sqrt(21))^n+(7+sqrt(21))^n]
cycle graph C_nL_n
empty graph K^__n2^n
gear graph2^n+(phi+1)^n+(phi+1)^(-n)
helm graph2^n+(1-sqrt(3))^n+(1+sqrt(3))^n
ladder graph1/2[(1-sqrt(2))^(n+1)+(1+sqrt(2))^(n+1)]
ladder rung graph nP_23^n
Möbius ladder M_n(-1)^(n+1)+(1-sqrt(2))^n+(1+sqrt(2))^n
pan graphF_(n+1)+L_n
path graph P_nF_(n+2)
prism graph Y_n(-1)^n+(1-sqrt(2))^n+(1+sqrt(2))^n
n×n rook graphn!L_n(-1)
star graph S_n2^(n-1)+1
sun graph2^(n-2)(n+4)
sunlet graph C_n circledot K_1(1-sqrt(3))^n+(1+sqrt(3))^n
wheel graph W_nL_(n-1)+1

See also

Clique, Edge Cover, Hungarian Maximum Matching Algorithm, Independent Set, Maximum Independent Vertex Set, Minimum Vertex Cover, Vertex Cover Number, Vertex Cover Polynomial

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.Skiena, S. S. "Vertex Cover." §8.5.3 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 317-318, 1997.Sloane, N. J. A. Sequences A002720, A006506, A027624, A051927, A063443, A141243, A182143, and A201862 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Vertex Cover

Cite this as:

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

Subject classifications