Vertex cover
Definition
Let be a graph. A vertex cover of is a set of vertices of that contains at least one end of each edge.
Remarks
A set is a vertex cover if and only if its complement is an independent set. For the complete bipartite graph , the least size of a vertex cover is . Each vertex of a cover meets at most one edge of a matching. Thus every vertex cover has at least as many vertices as any matching has edges.
Where this leads
2 pages build on this one.
Further reading
- Web https://en.wikipedia.org/wiki/Vertex_cover, Definition
About this page
| Tag | 0KDADE9RQ8 |
|---|---|
| URI | m2://0KDADE9RQ8 |
| Kind | definition |
| Writing | W1 stated |
| MSC | 05C70, 05C69 |
| Defines | Vertex cover |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge instance_of in: one example (0 of 1)
- edge not_instance_of in: one non-example that fails one clause (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.