Independent Domination
Dominating sets are closely related to independent sets: an independent set is also a dominating set if and only if it is a maximal independent set, so any maximal independent set in a graph is necessarily also a minimal dominating set. Thus, the smallest maximal independent set is also the smallest independent dominating set. The independent domination number i(G) of a graph G is the size of the smallest independent dominating set (or, equivalently, the size of the smallest maximal independent set).
The minimum dominating set in a graph will not necessarily be independent, but the size of a minimum dominating set is always less than or equal to the size of a minimum maximal independent set, that is, γ(G) ≤ i(G).
There are graph families in which a minimum maximal independent set is a minimum dominating set. For example, Allan & Laskar (1978) show that γ(G) = i(G) if G is a claw-free graph.
A graph G is called a domination-perfect graph if γ(H) = i(H) in every induced subgraph H of G. Since an induced subgraph of a claw-free graph is claw-free, it follows that every claw-free graphs is also domination-perfect (Faudree, Flandrin & Ryjáček 1997).
Read more about this topic: Dominating Set
Famous quotes containing the words independent and/or domination:
“It is so rare to meet with a man outdoors who cherishes a worthy thought in his mind, which is independent of the labor of his hands. Behind every man’s busy-ness there should be a level of undisturbed serenity and industry, as within the reef encircling a coral isle there is always an expanse of still water, where the depositions are going on which will finally raise it above the surface.”
—Henry David Thoreau (1817–1862)
“The will to domination is a ravenous beast. There are never enough warm bodies to satiate its monstrous hunger. Once alive, this beast grows and grows, feeding on all the life around it, scouring the earth to find new sources of nourishment. This beast lives in each man who battens on female servitude.”
—Andrea Dworkin (b. 1946)