K-Closure of a graph

[math]\displaystyle{ \,k }[/math]-Closure of a graph — [math]\displaystyle{ \,k }[/math]-Замыкание графа.

The [math]\displaystyle{ \,k }[/math]-closure [math]\displaystyle{ \,G_{k}(G) }[/math] of a graph [math]\displaystyle{ \,G }[/math] is obtained from [math]\displaystyle{ \,G }[/math] by recursively joining pairs of non-adjacent vertices whose degree-sum is at least [math]\displaystyle{ \,k }[/math] until no such pair remains. It is known that if [math]\displaystyle{ \,G_{n}(G) }[/math] is complete, then [math]\displaystyle{ \,G }[/math] contains a Hamiltonian cycle. The [math]\displaystyle{ \,k }[/math]-closure of a graph can be computed in [math]\displaystyle{ {\mathcal O}(n^{3}) }[/math] time in the worst case.

Литература

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