β-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 k -closure C k ( G ) , where k is a positive integer, of a graph G of order n as the graph obtained from G by recursively joining pairs of nonadjacent vertices a , b satisfying the condition d ( a ) + d ( b ) ≥ k . For many properties P , they found a suitable k (depending on P and n ) such that C k ( G ) has property P if and only if G does. In this paper we show that the condition d ( a ) + d ( b ) ≥ k can be replaced by a much better one: d ( a ) + d ( b ) + | Q ( G ) | ≥ k , where Q ( G ) is a well-defined subset of vertices nonadjacent to a , b .