VERTEX DOMINATION-CRITICAL GRAPHS

A graph G is vertex domination-critical if for any vertex v of G the d omination number of G - v is less than the domination number of G. If such a graph G has domination number gamma, it is called gamma-critica l. Brigham et al. studied gamma-critical graphs and posed the followin g questions: (1) If G is a gamma-critical graph, is \V\ greater than o r equal to (delta + 1)(gamma - 1) + 1? (2) if a gamma-critical graph G has (Delta + 1)(gamma - 1) + 1 vertices, is G regular? (3) Does i = g amma for all gamma-critical graphs? (4) Let d be the diameter of the g amma-critical graph G. Does d less than or equal to 2(gamma - 1) alway s hold? We show that the first and third questions have a negative ans wer and the others have a positive answer. (C) 1995 John Wiley and Son s, Inc.