Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
TOPICS
Search

Vertex Cover

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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.

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 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.

graph familyOEISnumber of vertex covers
antiprism graph for n>=3A000000X, X, 10, 21, 46, 98, 211, 453, 973, 2090, ...
n×n bishop graphA201862X, 9, 70, 729, 9918, 167281, ...
n×n black bishop graphA000000X, X, X, 27, 114, 409, 2066, ...
n-folded cube graphA000000X, 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>=2A000000X, 35, 70633, ...
n-halved cube graphA0000002, 3, 5, 13, 57, ...
n-Hanoi graphA0000004, 52, 108144, ...
hypercube graph Q_nA0276243, 7, 35, 743, 254475, 19768832143, ...
n×n king graphA063443X, 5, 35, 314, 6427, ...
n×n knight graphA141243X, 16, 94, 1365, 55213, ...
n-Möbius ladderA182143X, X, 15, 33, 83, 197, 479, 1153, 2787, ...
n-Mycielski graphA0000002, 3, 11, 103, 7407, ...
odd graph O_nA0000002, 4, 76, ...
prism graph Y_n for n>=3A051927X, X, 13, 35, 81, 199, 477, 1155, 2785, ...
n×n queen graphA0000002, 5, 18, 87, 462, ...
n×n rook graphA0027202, 7, 34, 209, 1546, 13327, 130922, ...
n-Sierpiński gasket graphA0000004, 14, 440, ...
n-triangular graphA000000X, 2, 4, 10, 26, 76, 232, 764, ...
n-web graph for n>=3A000000X, X, 68, 304, 1232, 5168, 21408, ...
n×n white bishop graphA000000X, 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, 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)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.

Referenced on Wolfram|Alpha

Vertex Cover

Cite this as:

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

Subject classifications