The Private Neighbor Cube

Abstract

Let S be a set of vertices in a graph $G = ( V,E )$. The authors state that a vertex u in S has a private neighbor (relative to S) if either u is not adjacent to any vertex in S or u is adjacent to a vertex w that is not adjacent to any other vertex in S. Based on the notion of private neighbors, a set of eight graph theoretic parameters can be defined whose inequality relationships can be described by a three-dimensional cube. Most of these parameters have already been studied independently. This paper unifies this study and helps to form a cohesive theory of private neighbors in graphs. Theoretical and algorithmic properties of this private neighbor cube are investigated, and many open questions are raised.