## 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 \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.

Original language | English |
---|---|

Pages (from-to) | 189-200 |

Number of pages | 12 |

Journal | Utilitas Mathematica |

Volume | 53 |

Publication status | Published - May 1998 |

Externally published | Yes |

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty
- Applied Mathematics