Paired Domination versus Domination and Packing Number in Graphs

Given a graph $G=(V(G),E(G))$, the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph $G$ are denoted by $\gamma (G)$, ${\gamma }_{\mathrm{p}\mathrm{r}}(G)$, and ${\gamma }_t(G)$, respectively. For a positive integer $k$, a $k$-packing in $G$ is a set $S \subseteq V(G)$suchthatforeverypairofdistinctvertices$u$and$v$in$S$,thedistancebetween$u$and$v$isatleast$k+1$\mathrm{.}The$k$-packing number is the order of a largest $k$-packing and is denoted by ${\rho }_k(G)$. It is well known that ${\gamma }_{\mathrm{p}\mathrm{r}}(G)\le 2\gamma (G)$. In this paper, we prove that it is NP-hard to determine whether ${\gamma }_{\mathrm{p}\mathrm{r}}(G)=2\gamma (G)$ even for bipartite graphs. We provide a simple characterization of trees with ${\gamma }_{\mathrm{p}\mathrm{r}}(G)=2\gamma (G)$, implying a polynomial-time recognition algorithm. We also prove that even for a bipartite graph, it is NP-hard to determine whether ${\gamma }_{\mathrm{p}\mathrm{r}}(G)={\gamma }_t(G)$. We finally prove that it is both NP-hard to determine whether ${\gamma }_{\mathrm{p}\mathrm{r}}(G)=2{\rho }_4(G)$ and whether ${\gamma }_{\mathrm{p}\mathrm{r}}(G)=2{\rho }_3(G)$.