Convex dominating set

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.