BUILT-IN MATHEMATICA SYMBOL

VertexCoverQ

yields True if the vertex list vlist is a vertex cover of the graph g, and False otherwise.

Test whether a set of vertices is a vertex cover in a graph:

Test for a directed graph:

Test whether a set of vertices is a vertex cover in a graph:

Out[1]=

Out[2]=

Test for a directed graph:

Out[1]=

Out[2]=

Test undirected graphs:

Directed graphs:

Enumerate all vertex covers for a cycle graph:

Enumerate all subsets of vertices and select the ones that are covers:

Highlight covers:

Enumerate all minimal vertex covers for a Petersen graph:

Find the size of a minimal vertex cover:

Enumerate all minimal vertex covers:

Highlight minimal covers:

The VertexList of a graph is a vertex (typically non-minimal) cover:

A smallest vertex cover can be found using FindVertexCover:

A set of vertices is a vertex cover iff its complement is an independent set:

Check that the complement set of vertices is independent:

The total size of the vertex cover and the largest independent set equals the vertex count:

The complement of the vertex cover in GraphComplement is a clique in its original graph:

Compute the complement using the same embedding:

Its complement is a clique:

The complete bipartite graph

has vertex cover of size

:

The largest independent edge set in a bipartite graph has the same size as the smallest vertex cover: