Domination in partitioned graphs with minimum degree two

Let V-1, V-2 be a partition of the vertex set in a. graph G. For i = 1, 2, let gamma(i) denote the least number of vertices needed in G to dominate V-i. It is known that if G has order n and minimum degree two, then gamma(1) + gamma(2) <= 2n/3. In this paper, we characterize those graphs of order n which are edge-minimal with respect to satisfying the conditions of connected, minimum degree at least two, and gamma(1) + gamma(2) = 2n/3. (c) 2006 Elsevier B.V. All rights reserved.