Maximal Independent Vertex Set

A maximal independent vertex set of a graph is an independent vertex set that cannot be expanded to another independent vertex set by addition of any vertex in the graph.

A maximal independent vertex set of a graph is equivalent to a maximal clique on the graph complement .

Note that a maximal independent vertex set is not equivalent to a maximum independent vertex set, which is an independent vertex set containing the largest possible number of vertices among all independent vertex sets. A maximum independent vertex set is always maximal, but the converse does not hold.

A maximal independent vertex set of a graph can be computed in the Wolfram Language using FindIndependentVertexSet[g, Infinity], and all maximal independent vertex sets can be computed using FindIndependentVertexSet[g, Infinity, All].

Wolfram Web Resources