Graph Utilities Package Symbol

MaximalIndependentVertexSet

MaximalIndependentVertexSet[g]
gives a maximal independent vertex set of an undirected graph g.

MaximalIndependentVertexSet[g, w]
gives a maximal independent vertex set of g with vertices weighted by w.

To use MaximalIndependentVertexSet, you first need to load the Graph Utilities Package using Needs["GraphUtilities`"].

MaximalIndependentVertexSet 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:

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:

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: