# Name for the set of vertices with the same neighborhood as another vertex

Suppose $\Gamma$ is a simple graph and $N_{\Gamma}(g)=\{x\in V(\Gamma)|x\sim g\}$ is the neighborhood of $g\in V(\Gamma)$. Then consider $$\mathbb{S}=\{y\in V(\Gamma)|N_{\Gamma}(y)=N_{\Gamma}(g)\}.$$ Is there a name in graph theory for the set $\mathbb{S}$?

• Every vertex in $\mathbb{S}$ is usually called a twin of $g$. – Tony Huynh Jan 20 '16 at 16:43

I suppose I will make my comment into an answer. The set of vertices with the same neighbourhood as a fixed vertex $g$, are called twins of $g$. If $x$ and $y$ are adjacent vertices of $\Gamma$ and $N_\Gamma(x) \cup \{x\}=N_\Gamma(y) \cup \{y\}$, then $x$ and $y$ are sometimes called adjacent twins. A nice use of adjacent twins is the Replication Lemma of Lovász, in his proof of the Weak Perfect Graph Conjecture.
Replication Lemma. Let $G$ be a perfect graph and $x \in V(G)$. If $G'$ is obtained from $G$ by adding a new vertex $y$ such that $x$ and $y$ are adjacent twins in $G'$, then $G'$ is also perfect.