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.