TransConj4.pdf (83.71 kB)
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)-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.
History
School
- Science
Department
- Computer Science
Published in
Discrete Applied MathematicsCitation
HUSSAK, W., 2016. Disjoint Hamilton cycles in transposition graphs. Discrete Applied Mathematics, 206, pp. 56-64.Version
- 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: https://creativecommons.org/licenses/by-nc-nd/4.0/Publication date
2016Notes
This paper was accepted for publication in the journal Discrete Applied Mathematics and the definitive published version is available at http://dx.doi.org/10.1016/j.dam.2016.02.007.ISSN
0166-218XPublisher version
Language
- en