Upper Irredundance Number

The upper irredundance number 👁 IR(G)
of a graph 👁 G
is the maximum size of an irredundant set of vertices in 👁 G
. It is therefore equal to the size of a maximum irredundant set as well to the size of a maximal irredundant set since every maximum irredundant set is also maximal. The upper irredundance number is also equal to largest exponent in a irredundance polynomial.

The (lower) irredundance number may be similarly defined as the minimum size of a maximal irredundant set of vertices in 👁 G
(Burger et al. 1997, Mynhardt and Roux 2020).

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 Number, Irredundance Polynomial, 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.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.

Referenced on Wolfram|Alpha

Upper Irredundance Number

Cite this as:

Weisstein, Eric W. "Upper Irredundance Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/UpperIrredundanceNumber.html

Subject classifications