Abstract: | 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 kth Bondy-Chvátal closure Clk(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 Clk(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. |