K-Cocomparability ordering

[math]\displaystyle{ \,k }[/math]-Cocomparability ordering — [math]\displaystyle{ \,k }[/math]-косравнимое упорядочение.

Let [math]\displaystyle{ \,G = (V,E) }[/math] be a graph and [math]\displaystyle{ \,k }[/math] a positive number. A [math]\displaystyle{ \,k }[/math]-cocomparability ordering (or [math]\displaystyle{ k }[/math]-CCPO) of [math]\displaystyle{ \,G }[/math] is an ordering of its vertices such that for every choice of vertices [math]\displaystyle{ \,u, v, w }[/math] we have the following:

[math]\displaystyle{ u \lt v \lt w \wedge d(u,w) \leq k \Rightarrow d(u,v) \leq k \vee d(v,w) \leq k. }[/math]

A graph [math]\displaystyle{ \,G }[/math] is called a [math]\displaystyle{ k }[/math]-cocomparability graph if it admits a [math]\displaystyle{ \,k }[/math]-CCPO.

Литература

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