Irredundant Set

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

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