Paired Domination versus Domination and Packing Number in Graphs

Abstract

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{pr}}(G)$, and ${\gamma }_t(G)$, respectively. For a positive integer $k$, a $k$-packing in $G$ is a set $S\subseteq V(G)$ such that for every pair of distinct vertices $u$ and $v$ in $S$, the distance between $u$ and $v$ is at least $k+1$. 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{pr}}(G)\le 2\gamma (G)$. In this paper, we prove that it is NP-hard to determine whether ${\gamma }_{\mathrm{pr}}(G)=2\gamma (G)$ even for bipartite graphs. We provide a simple characterization of trees with ${\gamma }_{\mathrm{pr}}(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{pr}}(G)={\gamma }_t(G)$. We finally prove that it is both NP-hard to determine whether ${\gamma }_{\mathrm{pr}}(G)=2{\rho }_4(G)$ and whether ${\gamma }_{\mathrm{pr}}(G)=2{\rho }_3(G)$.

14 pages, 8 figures