Maximum Independent Vertex Set

An independent vertex set of a graph  is a subset of the vertices such that no two vertices in the subset represent an edge of . Given a vertex cover of a graph, all vertices not in the cover define a independent vertex set (Skiena 1990, p. 218). A maximum independent vertex set is an independent vertex set containing the largest possible number of vertices for a given graph.

A maximum independent vertex set is not equivalent to a maximal independent vertex set, which is simply an independent vertex set that cannot be extended to a larger independent vertex set. Every maximum independent vertex set is also an independent vertex set, but the converse is not true.

The independence number of a graph is the cardinality of the maximum independent set.

Maximum independent vertex sets correspond to the complements of minimum vertex covers.

A maximum independent vertex set in a given graph  can be found in the Wolfram Language using FindIndependentVertexSet[g][[1]]. The command Sort[FindIndependentVertexSet[g, Length /@ FindIndependentVertexSet[g], All]] will find all maximum independent vertex sets.

REFERENCES

Myrvold, W. and Fowler, P. W. "Fast Enumeration of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput. 85, 173-194, 2013.

Pemmaraju, S. and Skiena, S. "Maximum Independent Set." §7.5.3 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 318, 2003.

Skiena, S. "Maximum Independent Set." §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.