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}$?

  • 5
    $\begingroup$ Every vertex in $\mathbb{S}$ is usually called a twin of $g$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.