---
tag: 3CZGXK7EWW
kind: concept
name: Dominating set
aliases: [dominating-set-problem, domination-number, domination-perfect-graph, independence-domination-number, independent-domination-number, minimum-dominating-set, total-dominating-set, total-domination-number]
sources:
  - wikipedia: en:1747972@r1374757470
    locator: Dominating set
    note: adopted
    mention: wikipedia://en/1747972
    sections: [Summary]
same_as:
  wikidata: Q2915204
  wikipedia: Dominating set
inventory: [JGQT0A10DW]
---

## Summary

In graph theory, a **dominating set** for a [[graph|00C0BR7D7H]] $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$.