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).

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.