Graphs: dominating sets
Place stations so that every point of the map is covered, and find the fewest that will do: the domination number of the graph.
- France: grade 12
- Iran: grade 12
- Russia: grade 7
Guide
Suppose cash machines go at some junctions of a town. Every junction must either have one or be one street away from one. We model this with a graph: junctions are vertices and streets are edges. A vertex in the set dominates itself and its neighbours.
A set of vertices is dominating if every vertex of the graph is in the set or next to a vertex of the set. The fewest vertices a dominating set can have is the domination number, written γ(G); a dominating set of that size is a minimum dominating set.
Minimal and minimum are different. A minimal set stops dominating if you remove any one vertex; a minimum set has the fewest vertices possible. Each vertex dominates at most Δ + 1 vertices (Δ is the biggest degree), so n vertices need at least the ceiling of n divided by Δ + 1. The ceiling means rounding up.