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:
“We are independent of the change we detect. The longer the lever, the less perceptible its motion. It is the slowest pulsation which is the most vital. The hero then will know how to wait, as well as to make haste. All good abides with him who waiteth wisely; we shall sooner overtake the dawn by remaining here than by hurrying over the hills of the west.”
—Henry David Thoreau (1817–1862)
“Physical nature lies at our feet shackled with a hundred chains. What of the control of human nature? Do not point to the triumphs of psychiatry, social services or the war against crime. Domination of human nature can only mean the domination of every man by himself.”
—Johan Huizinga (1872–1945)