[go: up one dir, main page]
TOPICS
Search

Minimal Vertex Cover

A minimal vertex cover is an vertex cover of a graph that is not a proper subset of any other vertex cover.

A minimal vertex cover corresponds to the complement of maximal independent vertex set, so the counts of minimal vertex covers and maximal independent vertex sets in a graph are identical.

Every minimum vertex cover is a minimal vertex cover, but the converse does not necessarily hold.

See also

Independent Vertex Set, Maximal Independent Vertex Set, Minimal Set, Minimum Vertex Cover, Vertex Cover

Explore with Wolfram|Alpha

Cite this as:

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

Subject classifications