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 G is equivalent to a maximal clique on the graph complement G'. 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.

independent vertex set | maximal clique | maximal set | maximum independent vertex set | well-covered graph

FindIndependentVertexSet