In graph theory, a paired dominating set of a graph is a dominating set of vertices such that the induced subgraph contains at least one perfect matching. The concept was introduced by Teresa W. Haynes and Peter J. Slater in 1998. The paired domination number, denoted , is the minimum cardinality of a paired dominating set of .
The concept models a situation in which guards are placed at vertices of a graph to dominate (protect) all vertices, with the additional constraint that each guard is assigned another adjacent guard as a backup. This is equivalent to finding a set of independent edges (a matching) whose endpoints form a dominating set.
Since every paired dominating set is a dominating set, and every dominating set whose induced subgraph has a perfect matching is necessarily a total dominating set, the following chain of inequalities holds for any graph without isolated vertices:
where is the domination number and is the total domination number.
Haynes and Slater characterized the triples of positive integers with for which there exists a graph satisfying , , and .
Because the endpoints of any maximal matching form a paired dominating set, the paired domination number is bounded above by twice the size of any maximal matching of the graph:
where denotes the size of a maximum matching.
Define the family as the set of graphs obtainable from three nonempty sets of parallel edges, , , and , by connecting each pair of vertices , , and with a path of length two (introducing a new vertex of degree two for each such pair). The original edges are called the associated matching of the resulting graph. When , the resulting graph is the cycle graph .
A connected, leafless graph of girth at least seven has a maximal matching whose endpoints form a minimum paired dominating set if and only if it belongs to the family .
A consequence of this characterization is that any such graph containing an 8-cycle must contain a specific 18-vertex graph, denoted , as an induced subgraph; this occurs precisely when at least two of the parameters are at least 2.
The problem of determining the paired domination number of a graph is NP-complete.