TOPICS
Search

Minimal Dominating Set

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A minimal dominating set is a dominating set in a graph that does not contain any other dominating set as a proper subset.

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 minimal connected dominating set need not be a minimal dominating set because deleting a vertex may leave a dominating set whose induced subgraph is a disconnected 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, Dominating Set, Domination Number, Minimal Connected Dominating Set, Minimal Set, Minimum Dominating Set

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

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.

Referenced on Wolfram|Alpha

Minimal Dominating Set

Cite this as:

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

Subject classifications