About MATtours
Site mapGallery of graphs and algorithmsHow to teach using investigationsClickable list of termsHelp


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.

red vertex dominates The red vertex dominates the black ones.
dominating set The red vertices are a dominating set for this graph.

Copyright © 1999-2000 SciMathMN