Star graph automorphisms and disjoint Hamilton cycles
journal contribution
posted on 2014-06-09, 10:59 authored by Parisa Derakhshan, Walter HussakWalter HussakThe search for edge-disjoint Hamilton cycles in star graphs is important for the design of interconnection network topologies. We define automorphisms for star graphs St n of degree n−1, for every positive odd integer n, which yield permutations of labels for the edges of St n taken from the set of integers between 1 and ⌊ n/2 ⌋. By decomposing these permutations into permutation cycles, we are able to identify edge-disjoint Hamilton cycles that are automorphic images of a known Hamilton cycle in St n . Our method produces a better than two-fold improvement from ⌊ ϕ (n)/10 ⌋ to ⌊ 2ϕ (n)/9 ⌋, where ϕ is the Euler function, for the known number of edge-disjoint Hamilton cycles in St n for all odd integers n. For prime n, the improvement is from ⌊ n/8 ⌋ to ⌊ n/5 ⌋, and we can extend this result to the case when n is the power of a prime greater than 7.
History
School
- Science
Department
- Computer Science
Citation
DERAKHSHAN, P. and HUSSAK, W., 2013. Star graph automorphisms and disjoint Hamilton cycles. International Journal of Computer Mathematics, 90 (3), pp. 483 - 496.Publisher
© Taylor and Francis LtdVersion
- VoR (Version of Record)
Publication date
2013Notes
This article is closed access, it was published in the serial International Journal of Computer Mathematics [© Taylor and Francis]. The definitive version is available at: http://dx.doi.org/10.1080/00207160.2012.741226ISSN
0020-7160Publisher version
Language
- en