Bondy-Chvatal closure operation

[math]\displaystyle{ Bondy-Chv\acute{a}tal }[/math] closure operation — операция замыкания Бонди-Хватала.

Given a graph of order [math]\displaystyle{ \,n }[/math], repeat the following operation as long as possible. For each pair of nonadjacent vertices [math]\displaystyle{ \,a }[/math] and [math]\displaystyle{ \,b }[/math], if [math]\displaystyle{ d(a) + d(b) \geq n }[/math], then add the edge [math]\displaystyle{ \,ab }[/math] to [math]\displaystyle{ G }[/math]. We denote by [math]\displaystyle{ \,cl(G) }[/math] the resulting graph and call it the [math]\displaystyle{ Bondy-Chv\acute{a}tal }[/math] closure of [math]\displaystyle{ \,G }[/math].

The other name is Hamiltonian closure.

Литература

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