TOPICS

# Dominating Set

For a graph and a subset of the vertex set , denote by the set of vertices in which are in or adjacent to a vertex in . If , then is said to be a dominating set (of vertices in ).

A dominating set of smallest size is called a minimum dominating set and its size is known as the domination number. A dominating set that is not a proper subset of any other dominating set is called a minimal dominating set.

For example, in the Petersen graph illustrated above, the set is a dominating set (and, in fact, a minimum dominating set).

The domination polynomial encodes the numbers of dominating sets of various sizes.

Other variants of the usual dominating set can be defined, including the so-called total dominating set.

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

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

Precomputed dominating sets for many named graphs can be obtained in the Wolfram Language using GraphData[graph, "DominatingSets"].

Connected Domination Number, Domatic Number, Domatic Partition,Dominance, Domination Number, Domination Polynomial, Minimal Dominating Set, Minimum Dominating Set, Total Dominating Set

Portions of this entry contributed by Nicolas Bray

## Explore with Wolfram|Alpha

More things to try:

## References

Alikhani, S. and Peng, Y.-H. "Introduction to Domination Polynomial of a Graph." Ars Combin. 114, 257-266, 2014.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.

Dominating Set

## Cite this as:

Bray, Nicolas and Weisstein, Eric W. "Dominating Set." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DominatingSet.html