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 ,

{v}]!=N_G[S]. " src="https://mathworld.wolfram.com/images/equations/IrredundantSet/NumberedEquation1.svg" style="height:21px; width:142px" />

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

---

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength