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:
“The chimney is to some extent an independent structure, standing on the ground, and rising through the house to the heavens; even after the house is burned it still stands sometimes, and its importance and independence are apparent.”
—Henry David Thoreau (1817–1862)
“... feminist solidarity rooted in a commitment to progressive politics must include a space for rigorous critique, for dissent, or we are doomed to reproduce in progressive communities the very forms of domination we seek to oppose.”
—bell hooks (b. c. 1955)