Exact n-step domination graph

Материал из WikiGrapp
Версия от 16:36, 26 апреля 2011; Glk (обсуждение | вклад) (Новая страница: «'''Exact <math>n</math>-step domination graph''' --- граф точного <math>n</math>-шагового доминирования. A vertex <math>u</math> in…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Exact [math]\displaystyle{ n }[/math]-step domination graph --- граф точного [math]\displaystyle{ n }[/math]-шагового доминирования.

A vertex [math]\displaystyle{ u }[/math] in a graph [math]\displaystyle{ G }[/math] is said to [math]\displaystyle{ n }[/math]-step dominate a vertex [math]\displaystyle{ v }[/math] if [math]\displaystyle{ d(u,v) = n }[/math]. If there exists a subset [math]\displaystyle{ S \subseteq V(G) }[/math] such that each [math]\displaystyle{ v \in V(G) }[/math] is [math]\displaystyle{ n }[/math]-step dominated by exactly one vertex in [math]\displaystyle{ S }[/math], then [math]\displaystyle{ G }[/math] is an exact [math]\displaystyle{ n }[/math]-step domination graph and [math]\displaystyle{ S }[/math] is called an exact [math]\displaystyle{ n }[/math]-step dominating set.