TOPICS
Search

Maximal Irredundant Set

A maximal irredundant set is an irredundant set that cannot be expanded to another irredundant set by addition of any vertex in the graph.

Note that a maximal irredundant set is not equivalent to a maximum irredundant set, which is an irredundant set containing the largest possible number of vertices among all irredundant sets. A maximum irredundant set is always maximal, but the converse does not hold.

If a set is dominating and irredundant, it is maximal irredundant and minimal dominating (Mynhardt and Roux 2020).

See also

Irredundant Set, Maximal Set, Maximum Irredundant Set

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.Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020. https://arxiv.org/abs/1812.03382.

Cite this as:

Weisstein, Eric W. "Maximal Irredundant Set." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MaximalIrredundantSet.html

Subject classifications