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 does not contain any other dominating set as a proper subset 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"].