Convex dominating set

Материал из WikiGrapp
Версия от 12:24, 25 января 2017; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Convex dominating setвыпуклое доминирующее множество.

A set [math]\displaystyle{ \,X \subseteq V(G) }[/math] is convex in [math]\displaystyle{ \,G }[/math] if vertices from all [math]\displaystyle{ \,(a-b) }[/math]-geodesics belong to [math]\displaystyle{ \,X }[/math] for any two vertices [math]\displaystyle{ \,a,b \in X }[/math]. A set [math]\displaystyle{ \,X }[/math] is a convex dominating set if it is convex and dominating. The convex domination number [math]\displaystyle{ \,\gamma_{con}(G) }[/math] of a graph [math]\displaystyle{ \,G }[/math] is the minimum cardinality of a convex dominating set in [math]\displaystyle{ \,G }[/math].

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.