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

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.