Paper Info
Title
Paired-domination in graphs
Abstract
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 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 protected, so we would want Us is an element of SN(s) = V(G). The (total) domination number gamma(G) (gamma(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 gamma(p)(G). This paper also contains results relating gamma(p)(G) to other domination parameters. For example, we note that gamma(G) less than or equal 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 & Sons, Inc.
Year
DOI
Venue
1998
10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F
NETWORKS
Field
DocType
Volume
Integer,Discrete mathematics,Dominating set,Combinatorics,Bound graph,Vertex (geometry),Induced subgraph,Matching (graph theory),Domination analysis,Connectivity,Mathematics
Journal
32
Issue
ISSN
Citations 
3
0028-3045
84
PageRank 
References 
Authors
8.59
0
2
Name
Order
Citations
PageRank
Teresa W. Haynes177494.22
Peter J. Slater2593132.02