THE PRIVATE NEIGHBOR CUBE

Let S be a set of vertices in a graph G = (V, E). The authors state th at 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,v that is not adjacent to any other vertex in S. Based on the notion of priv ate neighbors, a set of eight graph theoretic parameters can be define d whose inequality relationships can be described by a three-dimension al cube. Most of these parameters have already been studied independen tly. This paper unifies this study and helps to form a cohesive theory of private neighbors in graphs. Theoretical and algorithmic propertie s of this private neighbor cube are investigated, and many open questi ons are raised.