TOPICS
Search

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

ir(G)<=gamma(G)<=i(G)<=alpha(G)<=Gamma(G)<=IR(G)

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

Cite this as:

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

Subject classifications