In graph theory, a dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge. The domination number γ(G) is the number of vertices in a smallest dominating set for G.
The dominating set problem concerns testing whether γ(G) ≤ K for a given graph G and input K; it is a classical NP-complete decision problem in computational complexity theory (Garey & Johnson 1979). Therefore it is believed that there is no efficient algorithm that finds a smallest dominating set for a given graph.
Figures (a)–(c) on the right show three examples of dominating sets for a graph. In each example, each white vertex is adjacent to at least one red vertex, and it is said that the white vertex is dominated by the red vertex. The domination number of this graph is 2: the examples (b) and (c) show that there is a dominating set with 2 vertices, and it can be checked that there is no dominating set with only 1 vertex for this graph.
Read more about Dominating Set: History, Bounds, Independent Domination, Algorithms and Computational Complexity, Variants
Famous quotes containing the words dominating and/or set:
“... the selfishness that is bred of great success is our shame. We have subdued the wilderness and made it ours. We have conquered the earth and the richness thereof. We have indelibly stamped upon its face the seal of our dominating will. Now, unlike Alexander sighing for more worlds to conquer, we should address ourselves to adding beauty to that glory and grandeur.”
—Alice Foote MacDougall (1867–1945)
“Racism is when you have laws set up, systematically put in a way to keep people from advancing, to stop the advancement of a people. Black people have never had the power to enforce racism, and so this is something that white America is going to have to work out themselves. If they decide they want to stop it, curtail it, or to do the right thing ... then it will be done, but not until then.”
—Spike Lee (b. 1956)