The Algorithmic Complexity of Perfect Neighborhoods in Graphs

Abstract

Let $G$ be a graph and let $S$ be a subset of vertices of $G$. A vertex $v$ of $G$ is called perfect with respect to $S$ if $|N[v]\cap S|=1$, where $N[v]$ denotes the closed neighborhood of $v$. The set $S$ is defined to be a perfect neighborhood set of $G$ if every vertex of $G$ is perfect or adjacent with a perfect vertex.

The perfect neighborhood number $\theta (G)$ of $G$ is defined to be the minimum cardinality among all perfect neighborhood sets of $G$. In this paper, we present a variety of algorithmic results on the complexity of perfect neighborhood sets in graphs.