Disjoint Hamilton cycles in transposition graphs

Most network topologies that have been studied have been subgraphs of transposition graphs. Edge-disjoint Hamilton cycles are important in network topologies for improving fault-tolerance and distribution of messaging traffic over the network. Not much was known about edge-disjoint Hamilton cycles in general transposition graphs until recently Hung produced a construction of 4 edge-disjoint Hamilton cycles in the 5-dimensional transposition graph and showed how edge-disjoint Hamilton cycles in (n+1)(n+1)-dimensional transposition graphs can be constructed inductively from edge-disjoint Hamilton cycles in nn-dimensional transposition graphs. In the same work it was conjectured that nn-dimensional transposition graphs have n−1n−1 edge-disjoint Hamilton cycles for all nn greater than or equal to 5. In this paper we provide an edge-labelling for transposition graphs and, by considering known Hamilton cycles in labelled star subgraphs of transposition graphs, are able to provide an extra edge-disjoint Hamilton cycle at the inductive step from dimension nn to n+1n+1, and thereby prove the conjecture.