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 element S, N_G[S - {v}]!=N_G[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.

dominating set | graph neighborhood | irredundance number | irredundant Ramsey number | maximal irredundant set | maximum irredundant set | upper irredundance number