Irredundance Number

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

The upper irredundance number is defined as the maximum size of an irredundant set of vertices in G (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 ir(G), (lower) domination number gamma(G), lower independence number i(G), upper independence number alpha(G), upper domination number Gamma(G), and upper irredundance number IR(G) satsify the chain of inequalities


(Burger et al. 1997).

See also

Irredundance Polynomial, Irredundant Set, Upper Irredundance Number

Explore with Wolfram|Alpha


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.

Cite this as:

Weisstein, Eric W. "Irredundance Number." From MathWorld--A Wolfram Web Resource.

Subject classifications