Independent Dominating Set

An independent dominating set of a graph G is a set of vertices in G that is both an independent vertex set and a dominating set of G. Independent dominating sets are equivalent to maximal independent vertex sets.

The minimum size of an independent dominating set in a graph is known as its independent domination number (Crevals and Östergård 2015, Ilić and Milošević 2017). Since any maximal independent vertex set is also a minimal dominating set (Mynhardt and Roux 2020), the independent domination number is equivalent to the lower independence number.

See also

Dominating Set, Independent Vertex Set, Lower Independence Number

Explore with Wolfram|Alpha


Crevals, S. and Östergård, P. R. J. "Independent Domination of Grids." Disc. Math. 338, 1379-1384, 2015.Ilić, A. and Milošević, M. "The Parameters of Fibonacci and Lucas Cubes." Ars Math. Contemp. 12, 25-29, 2017.Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020.

Cite this as:

Weisstein, Eric W. "Independent Dominating Set." From MathWorld--A Wolfram Web Resource.

Subject classifications