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.