Dominating Set

graph-theory

Definition

Dominating Set

A dominating set of a graph $G=(V,E)$ is the set $D\subseteq V$, such that every vertex $v\in V$ is either in $D$ or adjacent to at least one $u\in D$.

Relation to Vertex Cover

Let $G=(V,E)$ be a graph with no isolated vertices. Every vertex cover of $G$ is also a dominating set of $G$.