PAIRED-DOMINATION IN GRAPHS

In a graph G = (V, E) if we think of each vertex s as the possible loc ation for a guard capable of protecting each vertex in its closed neig hborhood N[s], then ''domination'' requires every vertex to be protect ed. Thus, S subset of V(G) is a dominating set if Us is an element of SN[s] = V(G), For total domination, each guard must, in turn, be prote cted, so we would want Us is an element of SN(s) = V(G). The (total) d omination number gamma(G) (gamma(t)(G)) is the minimum cardinality tak en over all minimal (total) dominating sets of G. We introduce paired- domination for which each guard is assigned another adjacent one, and they are designated as backups for each other, that is, a paired-domin ating set is a dominating set whose induced subgraph contains at least one perfect matching. We show that the paired-domination problem is N P-complete and present bounds on the paired-domination number gamma(p) (G). This paper also contains results relating gamma(p)(G) to other do mination parameters. For example, we note that gamma(G) less than or e qual to gamma(t)(G) less than or equal to gamma(p)(G) and characterize those triples (a, b, c) of positive integers a less than or equal to b less than or equal to c for which there is a graph G having gamma(G) = a, gamma(t)(G) = b, and gamma(p)(G) = c, In addition, we introduce the concept of strong equality of parameters. (C) 1998 John Wiley & So ns, Inc.