Dominating set

Summary

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is in $D$ , or has a neighbor in $D$ . The domination number $\gamma(G)$ is the number of vertices in a smallest dominating set for $G$ .

Tag	`3CZGXK7EWW`
URI	`m2://3CZGXK7EWW`
Aliases	`dominating-set-problem`, `domination-number`, `domination-perfect-graph`, `independence-domination-number`, `independent-domination-number`, `minimum-dominating-set`, `total-dominating-set`, `total-domination-number`
Kind	concept
Writing	W1 stated
Same as	Wikidata Q2915204 Wikipedia Dominating set
Changed	4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W2

edge defines in: at least one definition (0 of 1)
edge instance_of in: at least two examples (0 of 2)
edge not_instance_of in: at least one non-example (0 of 1)
edge specializes both: the more general notions and the special cases (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.

Summary

Further reading

What this page needs for W2

What links here