Paired-Domination in Graphs
Document Type
Article
Publication Date
1-1-1998
Description
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∈SN[s] = V(G). For total domination, each guard must, in turn, be protected, so we would want ∪s∈SN(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.
Citation Information
Haynes, Teresa W.; and Slater, Peter J.. 1998. Paired-Domination in Graphs. Networks. Vol.32(3). 199-206. https://doi.org/10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F ISSN: 0028-3045