TransConj4.pdf (83.71 kB)

Disjoint Hamilton cycles in transposition graphs

Download (83.71 kB)
journal contribution
posted on 04.03.2016 by Walter Hussak
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)-dimensional transposition graphs can be constructed inductively from edge-disjoint Hamilton cycles in n-dimensional transposition graphs. In the same work it was conjectured that n-dimensional transposition graphs have n − 1 edge-disjoint Hamilton cycles for all n 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 n to n + 1, and thereby prove the conjecture.



  • Science


  • Computer Science

Published in

Discrete Applied Mathematics


HUSSAK, W., 2016. Disjoint Hamilton cycles in transposition graphs. Discrete Applied Mathematics, 206, pp. 56-64.


AM (Accepted Manuscript)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at:

Publication date



This paper was accepted for publication in the journal Discrete Applied Mathematics and the definitive published version is available at