Distance perfect neighborhoods in graphs

Let G be a graph and let S be a subset of vertices of G. Let s ≥ r ≥ 1 be integers. A vertex v of G is called r-perfect with respect to S if \N_r[v] ∩ S\ = 1 where N_r[v] denotes the closed r-neighborhood of v, i.e., N_r[v] is the set of all vertices within distance r from v. The set S is defined to be a (r, s)-perfect neighborhood set of G if every vertex of G is r-perfect or within distance s from an r-perfect vertex. The lower (upper) (r, s)-perfect neighborhood number θ_(r,s)(G) (respectively, Θ_(r,s)(G)) of G is defined to be the minimum (respectively, maximum) cardinality among all (r, s)-perfect neighborhood sets of G. In this paper, we present theoretical and computational results for (r, s)-perfect neighborhood sets of G. In particular, we prove that for all graphs G, γ_r+s(G) ≤ θ_(r,s)(G) ≤ γ_s(G) and Θ_(s,s)(G) = Γ_s(G), where γ_s(G) (Γ_s(G)) is the lower (upper) s-domination number of G. The decision problem corresponding to the problem of computing θ_(r,s)(G) is shown to be NP-complete, even when restricted to bipartite and chordal graphs.