Exact n-step domination graph

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

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.