This is documentation for Mathematica 6, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.1)

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.
  • MaximalIndependentVertexSet gives an (approximate) maximal set of vertices such the no two vertices form an edge. It treats the input as an undirected graph.
  • The length of the vector w must be the same as the number of vertices in g.