The d-distance p-packing domination number: complexity, cycles, and trees

Abstract A set of vertices $$X\subseteq V(G)$$ X ⊆ V ( G ) is a d -distance dominating set if for every $$u\in V(G)\setminus X$$ u ∈ V ( G ) \ X there exists $$x\in X$$ x ∈ X such that $$d(u,x) \le d$$ d ( u , x ) ≤ d , and X is a p -packing if $$d(u,v) \ge p+1$$ d ( u , v ) ≥ p + 1 for every different $$u,v\in X$$ u , v ∈ X . The d -distance p -packing domination number $$\gamma _d^p(G)$$ γ d p ( G ) of G is the minimum size of a set of vertices of G which is both a d -distance dominating set and a p -packing. It is proved that for every two fixed integers d and p with $$2 \le d$$ 2 ≤ d and $$0 \le p \le 2d-1$$ 0 ≤ p ≤ 2 d - 1 , the decision problem whether $$\gamma _d^p(G) \le k$$ γ d p ( G ) ≤ k holds is NP-complete for bipartite planar graphs. A necessary and sufficient condition for the existence of a d -distance p -packing dominating set in $$C_n$$ C n i