Paired dominating set

Short description: Set in graph theory

A graph with a minimum paired dominating set and a perfect matching of its induced subgraph colored red

In graph theory, a paired dominating set of a graph $G=(V,E)$ is a dominating set $S$ of vertices such that the induced subgraph $G[S]$ 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 ${\gamma }_p(G)$, is the minimum cardinality of a paired dominating set of $G$.

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 $M$ of independent edges (a matching) whose endpoints form a dominating set.

Properties and bounds

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 $G$ without isolated vertices:

$\gamma (G)\le {\gamma }_t(G)\le {\gamma }_p(G)$

where $\gamma (G)$ is the domination number and ${\gamma }_t(G)$ is the total domination number.

Haynes and Slater characterized the triples $(a,b,c)$ of positive integers with $a\le b\le c$ for which there exists a graph $G$ satisfying $\gamma (G)=a$, ${\gamma }_t(G)=b$, and ${\gamma }_p(G)=c$.

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:

${\gamma }_p(G)\le 2\nu (G)$

where $\nu (G)$ denotes the size of a maximum matching.

Define the family ${ℱ}$ as the set of graphs obtainable from three nonempty sets of parallel edges, $\{u_r{v}_r:r=1,\dots ,k\}$, $\{w_s{x}_s:s=1,\dots ,l\}$, and $\{y_t{z}_t:t=1,\dots ,m\}$, by connecting each pair of vertices $(v_r,w_s)$, $(x_s,y_t)$, and $(z_t,u_r)$ with a path of length two (introducing a new vertex of degree two for each such pair). The original $k+l+m$ edges are called the associated matching of the resulting graph. When $k=l=m=1$, the resulting graph is the cycle graph $C_9$.

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 $P_{18}$, as an induced subgraph; this occurs precisely when at least two of the parameters $k,l,m$ are at least 2.

Computational complexity

The problem of determining the paired domination number of a graph is NP-complete.