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.

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]=

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: