Double dominating set

Материал из WikiGrapp
Версия от 17:03, 5 апреля 2011; Glk (обсуждение | вклад) (Новая страница: «'''Double dominating set''' --- двойное доминирующее множество. A set <math>S \subset V(G)</math> is a '''double dominating set''' for …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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.