Paired‐domination in graphs

In a graph G = ( V , E ) if we think of each vertex s as the possible location for a guard capable of protecting each vertex in its closed neighborhood N [ s ], then “domination” requires every vertex to be protected. Thus, S ⊂ V ( G ) is a dominating set if ∪ s ∈ S N [ s ] = V ( G ). For total domination, each guard must, in turn, be protected, so we would want ∪ s ∈ S N ( s ) = V ( G ). The (total) domination number γ( G ) (γ t ( G )) is the minimum cardinality taken 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‐dominating set is a dominating set whose induced subgraph contains at least one perfect matching. We show that the paired‐domination problem is NP‐complete and present bounds on the paired‐domination number γ p ( G ). This paper also contains results relating γ p ( G ) to other domination parameters. For example, we note that γ( G ) ≤ γ t ( G ) ≤ γ p ( G ) and characterize those triples ( a , b , c ) of positive integers a ≤ b ≤ c for which there is a graph G having γ( G ) = a , γ t ( G ) = b , and γ p ( G ) = c . In addition, we introduce the concept of strong equality of parameters. © 1998 John Wiley & Sons, Inc. Networks 32: 199–206, 1998