Twin Vertices

Twin vertices are distinct vertices of a graph that have the same neighbors outside the pair. Thus vertices and are twins if

where denotes the open neighborhood of .

Two adjacent twin vertices are called true twins. Equivalently, they have the same closed neighborhoods, . Two nonadjacent twin vertices are called false twins. Equivalently, they have the same open neighborhoods, (Klavžar et al. 2023). Some sources call false twins duplicates and true twins coduplicates (Brandstadt et al. 1999).

Equality together with twinhood defines an equivalence relation on the vertex set. Swapping two twin vertices while fixing all other vertices is a graph automorphism. A twin-free graph is a graph in which every twin equivalence class is a singleton set.

A graph is a cograph iff every induced subgraph with at least two vertices contains a pair of twin vertices (Brandstadt et al. 1999). Twin classes are also graph modules in modular decomposition, but modules can be larger and need not consist entirely of pairwise twins.