VOOZH about

URL: https://mathworld.wolfram.com/MaximalIndependentVertexSet.html

⇱ Maximal Independent Vertex Set -- from Wolfram MathWorld

👁 Image

Maximal Independent Vertex Set

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

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.

A subset 👁 B subset V
of the vertex set 👁 V
of a graph is a maximally independent vertex set iff 👁 B
is both a dominating set and an independent vertex set (Burger et al. 1997).

Any maximal independent vertex set is also both minimal dominating and maximal irredundant (Mynhardt and Roux 2020). As a result, the lower independence number (which is the size of a smallest maximal independent vertex set) is equivalent to the independent domination number.

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

See also

Independent Vertex Set, Maximal Clique, Maximal Set, Maximum Independent Vertex Set, Well-Covered Graph

Explore with Wolfram|Alpha

References

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Hedetniemi, S. T. and Laskar, R. C. "A. Bibliography on Dominating Sets in Graphs and Some Basic Definitions of Domination Parameters." Disc. Math. 86, 257-277, 1990.Minty, G. J. "On Maximal Independent Sets of Vertices in Claw Free Graphs." J. Combin. Th. B 28, 284-304, 1980.Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020. https://arxiv.org/abs/1812.03382.Myrvold, W. and Fowler, P. W. "Fast Enumeration of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput. 85, 173-194, 2013.

Referenced on Wolfram|Alpha

Maximal Independent Vertex Set

Cite this as:

Weisstein, Eric W. "Maximal Independent Vertex Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MaximalIndependentVertexSet.html

Subject classifications