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

IndependentVertexSetQ

IndependentVertexSetQ
yields True if the vertex list vlist is an independent vertex set in the graph g and False otherwise.
  • An independent vertex set is a set of vertices that are never incident to the same edge.
Test whether a set of vertices is an independent vertex set:
Test for a directed graph:
Test whether a set of vertices is an independent vertex set:
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 independent vertex sets for a cycle graph:
Enumerate all subsets of vertices and select the ones that are independent vertex sets:
Highlight independent vertex sets:
Enumerate all maximal independent vertex sets for a Petersen graph:
Find the size of a maximal independent vertex set:
Enumerate all maximal independent vertex sets:
Highlight maximal independent sets:
A largest independent vertex set can be found using FindIndependentVertexSet:
The complement of an independent vertex set is a vertex cover:
The complement subgraph given by an independent vertex set is complete:
Bipartite graphs have equal-length edge covers and independent vertex sets:
New in 8