Define Dominating Set.

Question

In Graph Theory there are some problems such as "The Independent Set Problem", "Vertex Cover" and "Dominating Set". The ideas of the first two are pretty simple:

1. "The Independent Set Problem" deals with given a number of connected nodes, color in the nodes in such a way that no connected nodes have the same colors.

2. "Vertex Cover" deals with the fact that you're also given a certain amount of connected nodes, find the minimum amount of nodes that encompass all the connections.

My problem is with the "Dominating Set" because I can't find any good articles or videos that explain this properly.

Answer 1

Here is a clear statement of the problem (the statement might be clear if you are already familiar with the vertex cover problem):

Dominating Set: input undirected $G$, integer $k > 0$. Is there a subset of vertices $S$, $|S|\leq k$, that dominates all vertices?

A very clear (at least to me) definition of a dominating set is found here:

A dominating set in a graph $G$ is a subset of vertices $S \subseteq V$ such that each vertex in $V$ is either in $S$ or is adjacent to some vertex in $S$.