TOPICS
Search

Minimal Dominating Set

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A minimal dominating set is a dominating set in a graph that is not a proper subset of any other dominating set.

Every minimum dominating set is a minimal dominating set, but the converse does not necessarily hold.

Minimal dominating sets can be used to compute the domatic number of a graph.

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

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

See also

Domatic Number, Domination Number, Dominating Set, Minimal Set, Minimum Dominating Set

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

Cite this as:

Weisstein, Eric W. "Minimal Dominating Set." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MinimalDominatingSet.html

Subject classifications