THE DIAMETER OF DOMINATION K-CRITICAL GRAPHS

A graph is k-domination-critical if gamma(G) = k, and for any edge e n ot in G, gamma(G + e) = k - 1. In this paper we show that the diameter of a domination k-critical graph with k greater-than-or-equal-to 2 is at most 2k - 2. We also show that for every k greater-than-or-equal-t o 2, there is a k-domination-critical graph having diameter [(3/2)k - 1]. We also show that the diameter of a 4-domination-critical graph is at most 5. (C) 1994 John Wiley & Sons, Inc.