BICLOSURE AND BISTABILITY IN A BALANCED BIPARTITE GRAPH

The k-biclosure of a balanced bipartite graph with color classes A and B is the graph obtained from G by recursively joining pairs of nonadj acent vertices respectively taken in A and B whose degree sum is at le ast k, until no such pair remains. A property P defined on all the bal anced bipartite graphs of order 2n is k-bistable if whenever G + ab ha s property P and d(G)(a) + d(G)(b) greater than or equal to k then G i tself has property P. We present a synthesis of results involving, for some properties P, the bistability of P, the k-biclosure of G, the nu mber of edges and the minimum degree. (C) 1995 John Wiley & Sons, Inc.