INDEPENDENCE AND HAMILTONICITY IN 3-DOMINATION-CRITICAL GRAPHS

Let delta, gamma, i and alpha be respectively the minimum degree, the domination number, the independent domination number and the independe nce number of a graph G. The graph G is 3-gamma-critical if gamma = 3 and the addition of any edge decreases gamma by 1. It was conjectured that any connected 3-gamma-critical graph satisfies i = gamma, and is hamiltonian if delta greater than or equal to 2. We show here that eve ry connected 3-gamma-critical graph G with delta greater than or equal to 2 satisfies alpha less than or equal to delta + 2; if alpha = delt a + 2 then i = gamma; while if alpha less than or equal to delta + 1 t hen G is hamiltonian. (C) 1997 John Wiley & Sons, Inc.