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 ≤ 2n − 3 such that the k th Bondy‐Chvátal closure Cl k ( G ) is complete, and give some necessary or 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 then G satisfies P. For some properties P , we compare cs( P ) with the classical stability s( P ) of P and show that cs( P ) may be far smaller than s( P ). © 1993 John Wiley & Sons, Inc.