Double Occurrence Words with the Same Alternance Graph

Abstract

Let $m$ be a double occurrence word (i.e., each letter occurring in $m$ occurs precisely twice). An alternance of $m$ is a non-ordered pair $uw$ of distinct letters such that we meet alternatively $\dots v\dots w\dots v\dots w\dots$ when reading $m$. The alternance graph $A(m)$ is the simple graph whose vertices are the letters of $m$ and whose edges are the alternances of $m$. We define a transformation of double occurrence words such that whenever $A(m)=A(n)$, $m$ and $n$ are related by a sequence of these transformations.