Star graph automorphisms and disjoint Hamilton cycles

Abstract

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.

Keywords:

• star graph
• symmetric group
• interconnection network topologies

2010 AMS Subject Classifications::

• 05C38
• 05C45
• 68R10