Paired-domination in graphs

✍ Scribed by Haynes, Teresa W.; Slater, Peter J.

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 145 KB
• Volume: 32
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199810)32:3<199::aid-net4>3.0.co;2-f

✦ Synopsis

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(G) (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 g p (G). This paper also contains results relating g p (G) to other domination parameters. For example, we note that g(G) °gt (G) °gp (G) and characterize those triples ( a, b, c) of positive integers a °b °c for which there is a graph G having g(G) Å a, g t (G) Å b, and g p (G) Å c. In addition, we introduce the concept of strong equality of parameters. ᭧ 1998