Irredundant Set

The concept of irredundance was introduced by Cockayne et al. (1978). Let N_G[v] denote the graph neighborhood of a vertex v in a graph G (including v itself), and let N_G[S] denote the union of neighborhoods for a set of vertices S. Then A set of vertices S in a graph G is called an irredundant set if, for every vertex v in S,


In other words, an irredundant set is a set of graph vertices such that the removal of any single vertex from the set gives a different union of neighborhoods than the union of neighborhood for the entire set.

An irredundant set of largest possible size is called a maximum irredundant set, and an irredundant set that is not a proper subset of a larger irredundant set is called a maximal irredundant set.

Any independent vertex set is an irredundant set (Burger et al. 1997, Mynhardt and Roux 2020).

A dominating set is minimal dominating iff it is irredundant (Mynhardt and Roux 2020).

If a set is irredundant and dominating, it is maximal irredundant and minimal dominating (Mynhardt and Roux 2020).

See also

Dominating Set, Graph Neighborhood, Irredundance Number, Irredundant Ramsey Number, Maximal Irredundant Set, Maximum 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.Chartrand, G. and Lesniak, L. Graphs & Digraphs, 4th ed. Boca Raton, FL: Chapman & Hall/CRC, pp. 286-287, 2005.Cockayne, E. J. Hedetniemi, S. T.; and Miller, D. J. "Properties of Hereditary Hypergraphs and Middle Graphs." Canad. Math. Bull. 21< 461-468, 1978.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. "Irredundant Set." From MathWorld--A Wolfram Web Resource.

Subject classifications