Distance perfect neighborhoods in graphs
Abstract
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 \Nr[v] ∩ S\ = 1 where Nr[v] denotes the closed r-neighborhood of v, i.e., Nr[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.
