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

Abstract A set of vertices X V (G) X ⊆ V (G) is a d -distance dominating set if for every u V (G) X u ∈ V (G) \ X there exists x X x ∈ X such that d (u, x) d d (u, x) ≤ d, and X is a p -packing if d (u, v) p+1 d (u, v) ≥ p + 1 for every different u, v X u, v ∈ X. The d -distance p -packing domination number dᵖ (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 d 2 ≤ d and 0 p 2d-1 0 ≤ p ≤ 2 d - 1, the decision problem whether dᵖ (G) 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ₙ C n i