THE COMPLETE CLOSURE OF A GRAPH

We define the complete closure number cc(G) of a graph G of order n as the greatest integer k less-than-or-equal-to 2n - 3 such that the kth Bondy-Chvatal closure Cl(k)(G) is complete, and give some necessary o r sufficient conditions for a graph to have cc(G) = k. Similarly, the complete stability cs(P) of a property P defined on all the graphs of order n is the smallest integer k such that if Cl(k)(G) is complete th en G satisfies P. For some properties P, we compare cs(P) with the cla ssical stability s(P) of P and show that cs(P) may be far smaller than s(P). (C) 1993 John Wiley & Sons, Inc.