Double dominating set

Double dominating set --- двойное доминирующее множество.

A set [math]\displaystyle{ S \subset V(G) }[/math] is a double dominating set for [math]\displaystyle{ G }[/math] if every vertex in [math]\displaystyle{ V }[/math] is dominated by at least two vertices in [math]\displaystyle{ S }[/math]. The minimum cardinality of a double dominating set is a double domination number, denoted [math]\displaystyle{ dd(G) }[/math]. Obviously, every double dominating set is also a dominating set. Note that the concept of double domination can be extended to multiple domination ([math]\displaystyle{ h }[/math]-tuple domination) by requiring that each vertex in [math]\displaystyle{ V }[/math] be dominated at least [math]\displaystyle{ h }[/math] times.

The concept of double domination in graphs was defined by Harary and Haynes (2002).

A double dominating set is exact if every vertex of [math]\displaystyle{ G }[/math] is dominated exactly twice. The problem of existence of an exact double dominating set is an NPcomplete problem.