This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.
 GRAPH UTILITIES PACKAGE SYMBOL

# MaximalIndependentVertexSet

 MaximalIndependentVertexSet[g]gives a maximal independent vertex set of an undirected graph g. gives a maximal independent vertex set of g with vertices weighted by w.
• gives an (approximate) maximal set of vertices such that no two vertices form an edge. It treats the input as an undirected graph.
• The length of the vector w must be the same as the number of vertices in g.
This specifies a small graph:
This shows that the maximal independent vertex set contains three vertices:
This plots the graph's maximal independent vertex set highlighted in red circles:
This finds a maximal independent vertex set with preference given to vertices with even labels:
This plots the new graph's maximal independent vertex set highlighted in red circles:
Needs["GraphUtilities`"]
This specifies a small graph:
 Out[3]=
This shows that the maximal independent vertex set contains three vertices:
 Out[4]=
This plots the graph's maximal independent vertex set highlighted in red circles:
 Out[5]=
This finds a maximal independent vertex set with preference given to vertices with even labels:
 Out[6]=
This plots the new graph's maximal independent vertex set highlighted in red circles:
 Out[7]=
 Applications   (1)
This is a matrix representation of the graph of a torus:
This finds the maximal independent vertex set of the torus:
This plots the torus, with the maximal independent vertex set in red: