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:
“There is in fact no such thing as art for art’s sake, art that stands above classes, art that is detached from or independent of politics. Proletarian literature and art are part of the whole proletarian revolutionary cause.”
—Mao Zedong (1893–1976)
“Let us be aware that while they preach the supremacy of the state, declare its omnipotence over individual man, and predict its eventual domination of all peoples of the earth—they are the focus of evil in the modern world.”
—Ronald Reagan (b. 1911)