Transposition Graphs

Abstract

The transposition graph $G(p_1 , \cdots ,p_k )$ is a regular graph having as vertices all sequences of $p_1 + \cdots + p_k $ symbols, of which $p_1 $ are of kind $1, \cdots ,p_k $ are of kind k. Two vertices are adjacent if transposing a pair of different symbols in one gives the other. We justify CACM Algorithms 382 and 383, which generate Hamilton paths in $G(p_1 , \cdots ,p_k )$. The main result is that $G(p_1 , \cdots ,p_k )$ is Hamiltonian.