Detour dominating set

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

Detour dominating set --- обходное доминирующее множество.

For a vertex v in G, define

D^{-}(v) = \min \{D(u,v): u \in V(G) - \{v\}\}.

A vertex u (\neq v) is called a detour neighbor of v if D(u,v) = D^{-}(v). The detour neighborhood N_{D}(v) of a vertex v is the set of detour neighbors of v, and its closed detour neighborhood is N_{D}[v] = N_{D}(v) \cup \{v\}. A vertex v is said to detour-dominate a vertex u if u = v or u is a detour neighbor of v.