Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $

Abstract

Let B be a basis of transpositions for $S_n $ and let Cay$( B:S_n )$ be the Cayley graph of $S_n $ with respect to B. It was shown by Kompel’makher and Liskovets [Kibemetica, 3 (1975), pp. 17–21] that Cay$( B:S_n )$ is Hamiltonian. This result is extended as follows. Note that every transposition b in B induces a perfect matching $M_b $ in Cay$( B:S_n )$. It is shown here when $n > 4$ that, for any $b \in B$, there is a Hamilton cycle in Cay$( B:S_n )$ that includes every edge of $M_b $. That is, for $n > 4$, for any basis B of transpositions of $S_n $, and, for any $b \in B$, it is possible to generate all permutations of $1,2, \ldots ,n$ by transpositions in B so that every other transposition is b.