Loughborough University

File(s) under permanent embargo

Reason: This item is currently closed access.

Star graph automorphisms and disjoint Hamilton cycles

journal contribution
posted on 2014-06-09, 10:59 authored by Parisa Derakhshan, Walter HussakWalter Hussak
The 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.



  • Science


  • Computer Science


DERAKHSHAN, P. and HUSSAK, W., 2013. Star graph automorphisms and disjoint Hamilton cycles. International Journal of Computer Mathematics, 90 (3), pp. 483 - 496.


© Taylor and Francis Ltd


  • VoR (Version of Record)

Publication date



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.741226




  • en