Dominating set

In graph theory, a **dominating set** for a graph \( G = (V, E) \) is a subset \( D \subseteq V \) of the vertices such that every vertex not in \( D \) is adjacent to at least one vertex in \( D \).

There are no discussions about this article yet.

 Articles by others on the same topic (1)

D

of a graph is a vertex subset such that every unselected vertex has a neighbour in

D

. Equivalently every vertex lies in

D

or is adjacent to an element of

D

. This condition differs from vertex cover, which requires every edge to have an endpoint in the selected set.