Irredundant Set

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

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.

The (lower) irredundance number 👁 ir(G)
of a graph 👁 G
is the minimum size of a maximal irredundant set of vertices in 👁 G
, while the upper irredundance number is the size of a maximum 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

References

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

Referenced on Wolfram|Alpha

Irredundant Set

Cite this as:

Weisstein, Eric W. "Irredundant Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/IrredundantSet.html

Subject classifications