Dominating Set

graph-theory

Definition

Dominating Set

A dominating set of a graph is the set , such that every vertex is either in or adjacent to at least one .

Example: In the graph below, the set is a dominating set, as every vertex either lies in or is adjacent to or .

Relation to Vertex Cover

Let be a graph with no isolated vertices. Every vertex cover of is also a dominating set of .

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 is a dominating set, since both and are adjacent to , but it is not a vertex cover, since the edge is not incident to .