Skip to content
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Publication Details
AFRICAN RESEARCH NEXUS
SHINING A SPOTLIGHT ON AFRICAN RESEARCH
computer science
Paired-domination in graphs
Networks, Volume 32, No. 3, Year 1998
Notification
URL copied to clipboard!
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. © 1998 John Wiley & Sons, Inc.
Authors & Co-Authors
Haynes, Teresa W.
United States, Johnson
East Tennessee State University
Slater, Peter J.
United States, Huntsville
The University of Alabama in Huntsville
Statistics
Citations: 195
Authors: 2
Affiliations: 2
Identifiers
Doi:
10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F
ISSN:
00283045
Study Design
Case-Control Study