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 graph neighborhood of .

For distinct twin vertices and , there are two cases. If , they are true twins, equivalently . If , they are false twins, equivalently (Klavžar et al. 2023). Thus the first case uses closed neighborhoods and the second uses open graph neighborhoods. Some sources call false twins duplicates and true twins coduplicates (Brandstädt 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 (Brandstädt 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. Pairwise twinhood would require every two distinct vertices in the module to be twins.