TOPICS
Search

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

 R_G(x)=sum_(k=1)^(|V(G)|)i_k(G)x^k.

It may also be written as

 R_G(x)=sum_(k=1)^(IR(G))i_k(G)x^k,

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

References

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. https://arxiv.org/abs/1812.03382.

Cite this as:

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

Subject classifications