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$.

Example: In the graph below, the set $D=\{v_2,v_4\}$ is a dominating set, as every vertex either lies in $D$ or is adjacent to $v_2$ or $v_4$.

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$.

Difference to Vertex Cover

A vertex cover controls edges: every edge must be incident to at least one selected vertex. A dominating set controls vertices: every vertex must either be selected or adjacent to a selected vertex. Thus a vertex cover is stronger, because it directly covers all edges, whereas a dominating set only needs to reach all vertices.

The converse therefore fails in general. In the graph below, the set $D=\{v_1\}$ is a dominating set, since both $v_2$ and $v_3$ are adjacent to $v_1$, but it is not a vertex cover, since the edge $v_2{v}_3$ is not incident to $v_1$.