Mathematica 9 is now available
THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.
Wolfram Mathematica Documentation Center
DOCUMENTATION CENTER SEARCH
New to Mathematica? Find your learning path »
Mathematica > Mathematics and Algorithms > Graphs & Networks > Graph Covers and Independent Sets > FindVertexCover >
Mathematica > Visualization and Graphics > Graphs & Networks > Graph Covers and Independent Sets > FindVertexCover >
BUILT-IN MATHEMATICA SYMBOLSee Also »|More About »

FindVertexCover

FindVertexCover[g]
finds a vertex cover of the graph g with a minimum number of vertices.
MORE INFORMATION
  • A vertex cover is a set of vertices that is incident to every edge.
EXAMPLESCLOSE ALL
Basic Examples   (2)
Find a vertex cover in a complete graph:
Find a vertex cover in a directed graph:
Find a vertex cover in a complete graph:
In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=
 
Find a vertex cover in a directed graph:
In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=
Scope   (2)
FindVertexCover works with undirected graphs:
Directed graphs:
Properties & Relations   (6)
The result of FindVertexCover can be tested by VertexCoverQ:
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
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team
Format:   HTML  |  CDF