TOPICS

# Irredundance Number

The (lower) irredundance number of a graph is the minimum size of a maximal irredundant set of vertices in .

The upper irredundance number is defined as the maximum size of an irredundant set of vertices in (Burger et al. 1997, Mynhardt and Roux 2020). In other words, it is the size of a maximum irredundant set, which is the same as the maximum size of a maximal irredundant set since all maximum irredundant sets are also maximal.

The (lower) irredundance number , (lower) domination number , lower independence number , upper independence number , upper domination number , and upper irredundance number satsify the chain of inequalities

(Burger et al. 1997).

Irredundance Polynomial, Irredundant Set, Upper Irredundance Number

## Explore with Wolfram|Alpha

More things to try:

## References

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Cockayne, E. J. and Mynhardt, C. M. "The Sequence of Upper and Lower Domination, Independence and Irredundance Numbers of a Graph." Disc. Math. 122, 89-102, 1993).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. "Irredundance Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IrredundanceNumber.html