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 ability to secure an independent livelihood and honorable employ suited to her education and capacities is the only true foundation of the social elevation of woman, even in the very highest classes of society. While she continues to be educated only to be somebody’s wife, and is left without any aim in life till that somebody either in love, or in pity, or in selfish regard at last grants her the opportunity, she can never be truly independent.”
—Catherine E. Beecher (1800–1878)
“All personal, psychological, social, and institutionalized domination on this earth can be traced back to its source: the phallic identities of men.”
—Andrea Dworkin (b. 1946)