In a graph, a vertex is said to dominate each of the vertices adjacent to it. A dominating set of a graph is the collection of vertices which together dominate all of the other vertices in the graph.
A graph can have numerous different dominating sets of varying sizes. Often it is interesting to know what the smallest possible dominating set for a graph is. This is called a minimal dominating set, and the number of vertices in such a set is called the dominating number.
|The red vertex dominates the black ones.|
|The red vertices are a dominating set for this graph.|
Copyright © 1999-2000 SciMathMN