Irredundance Polynomial

Let i_k(G) be the number of irredundant sets of size k in a graph G, then the irredundance polynomial R_G(x) of G in the variable x is defined as


It may also be written as


where IR(G) is the upper irredundance number of G (cf. Burger et al. 1997, Mynhardt and Roux 2020).

See also

Irredundance Number, 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.Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020.

Cite this as:

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

Subject classifications