Paired dominating set

In graph theory, a paired dominating set of a graph ${\displaystyle G=(V,E)}$ is a dominating set ${\displaystyle S}$ of vertices such that the induced subgraph ${\displaystyle 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 ${\displaystyle \gamma _{p}(G)}$, is the minimum cardinality of a paired dominating set of ${\displaystyle 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 ${\displaystyle M}$ 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 ${\displaystyle G}$ without isolated vertices:¹

${\displaystyle \gamma (G)\leq \gamma _{t}(G)\leq \gamma _{p}(G)}$

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

Haynes and Slater characterized the triples ${\displaystyle (a,b,c)}$ of positive integers with ${\displaystyle a\leq b\leq c}$ for which there exists a graph ${\displaystyle G}$ satisfying ${\displaystyle \gamma (G)=a}$, ${\displaystyle \gamma _{t}(G)=b}$, and ${\displaystyle \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:²

${\displaystyle \gamma _{p}(G)\leq 2\,\nu (G)}$

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

Define the family ${\displaystyle {\mathcal {F}}}$ as the set of graphs obtainable from three nonempty sets of parallel edges, ${\displaystyle \{u_{r}v_{r}:r=1,\ldots ,k\}}$, ${\displaystyle \{w_{s}x_{s}:s=1,\ldots ,l\}}$, and ${\displaystyle \{y_{t}z_{t}:t=1,\ldots ,m\}}$, by connecting each pair of vertices ${\displaystyle (v_{r},w_{s})}$, ${\displaystyle (x_{s},y_{t})}$, and ${\displaystyle (z_{t},u_{r})}$ with a path of length two (introducing a new vertex of degree two for each such pair). The original ${\displaystyle k+l+m}$ edges are called the associated matching of the resulting graph. When ${\displaystyle k=l=m=1}$, the resulting graph is the cycle graph ${\displaystyle 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 ${\displaystyle {\mathcal {F}}}$.²

A consequence of this characterization is that any such graph containing an 8-cycle must contain a specific 18-vertex graph, denoted ${\displaystyle P_{18}}$, as an induced subgraph; this occurs precisely when at least two of the parameters ${\displaystyle k,l,m}$ are at least 2.²

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