Paired domination versus domination and packing number in graphs

Given a graph $$G=(V(G), E(G))$$ 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)$$ γ ( G ) , $$\gamma _{pr}(G)$$ γ pr ( G ) , and $$\gamma _{t}(G)$$ γ t ( G ) , respectively. For a positive integer k, a k-packing in G is a set $$S \subseteq V(G)$$ S ⊆ 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$$ k + 1 . The k-packing number is the order of a largest k-packing and is denoted by $$\rho _{k}(G)$$ ρ k ( G ) . It is well known that $$\gamma _{pr}(G) \le 2\gamma (G)$$ γ pr ( G ) ≤ 2 γ ( G ) . In this paper, we prove that it is NP-hard to determine whether $$\gamma _{pr}(G) = 2\gamma (G)$$ γ pr ( G ) = 2 γ ( G ) even for bipartite graphs. We provide a simple characterization of trees with $$\gamma _{pr}(G) = 2\gamma (G)$$ γ pr ( G ) = 2 γ ( G ) , implying a polynomial-time recognition algorithm. We also prove that even for a bipartite graph, it is NP-hard to determine whether $$\gamma _{pr}(G)=\gamma _{t}(G)$$ γ pr ( G ) = γ t ( G ) . We finally prove that it is both NP-hard to determine whether $$\gamma _{pr}(G)=2\rho _{4}(G)$$ γ pr ( G ) = 2 ρ 4 ( G ) and whether $$\gamma _{pr}(G)=2\rho _{3}(G)$$ γ pr ( G ) = 2 ρ 3 ( G ) .