Graph Concepts

Dominating

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.

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