Vertex Cover Number
The vertex cover number is the size of a minimum vertex cover in a graph G is known as the vertex cover number of G, denoted tau(G).
The König-Egeváry theorem states that the matching number (i.e., size of a maximum independent edge set) and vertex cover number are equal for a bipartite graph.
The independence number alpha(G) of a graph G and vertex cover number are related by
| alpha(G)+tau(G)=|G|, |
where n=|G| is the vertex count (West 2000).
See also
Independence Number, Minimum Vertex Cover, Vertex Cover, Vertex Cover PolynomialExplore with Wolfram|Alpha
WolframAlpha
More things to try:
References
West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.Referenced on Wolfram|Alpha
Vertex Cover NumberCite this as:
Weisstein, Eric W. "Vertex Cover Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/VertexCoverNumber.html