ββ-degree closures for graphs

Bondy and Chvátal [J.A. Bondy, V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111–135] introduced a general and unified approach to a variety of graph-theoretic problems. They defined the kk-closure Ck(G)Ck(G), where kk is a positive integer, of a graph GG of order nn as the graph obtained from GG by recursively joining pairs of nonadjacent vertices a,ba,b satisfying the condition d(a)+d(b)≥kd(a)+d(b)≥k. For many properties PP, they found a suitable kk (depending on PP and nn) such that Ck(G)Ck(G) has property PP if and only if GG does. In this paper we show that the condition d(a)+d(b)≥kd(a)+d(b)≥k can be replaced by a much better one: d(a)+d(b)+|Q(G)|≥kd(a)+d(b)+|Q(G)|≥k, where Q(G)Q(G) is a well-defined subset of vertices nonadjacent to a,ba,b.