This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.2)

VertexCoverQ

VertexCoverQ
yields True if the vertex list vlist is a vertex cover of the graph g, and False otherwise.
  • A vertex cover is a set of vertices that is incident to every edge.
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:
In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=
 
Test for a directed graph:
In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
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:
New in 8