Maximum Independent Vertex Set
An independent vertex set of a graph 👁 G
is a subset of the vertices such that no two vertices in the
subset represent an edge of 👁 G
. 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 👁 g
can be found in the Wolfram Language
using [g][[1]].
The command [[g,
g, ]] will
find all maximum independent vertex sets.
See also
Independence Number, Independent Set, Independent Vertex Set, Maximal Independent Vertex Set, Maximum Independent Edge Set, Maximum Independent Set Problem, Minimum Vertex Cover, Vertex CoverExplore with Wolfram|Alpha
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.Referenced on Wolfram|Alpha
Maximum Independent Vertex SetCite this as:
Weisstein, Eric W. "Maximum Independent Vertex Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MaximumIndependentVertexSet.html