Optimal bounds for disjoint Hamilton cycles in star graphs
journal contributionposted on 27.06.2017, 13:14 by Parisa Derakhshan, Walter Hussak
In interconnection network topologies, the n-dimensional star graph Stn has n! vertices corresponding to permutations a (1) : : : a (n) of n symbols a1; : : : ; an and edges which exchange the positions of the rst symbol a (1) with any one of the other symbols. The star graph compares favorably with the familiar n-cube on degree, diameter and a number of other parameters. A desirable property which has not been fully evaluated in star graphs is the presence of multiple edge-disjoint Hamilton cycles which are important for fault-tolerance. The only known method for producing multiple edge-disjoint Hamilton cycles in Stn has been to label the edges in a certain way and then take images of a known base 2-labelled Hamilton cycle under di erent automorphisms that map labels consistently. However, optimal bounds for producing edge-disjoint Hamilton cycles in this way, and whether Hamilton decompositions can be produced, are not known for any Stn other than for the case of St5 which does provide a Hamilton decomposition. In this paper we show that, for all n, not more than '(n)=2, where ' is Euler's totient function, edge-disjoint Hamilton cycles can be produced by such automorphisms. Thus, for non-prime n, a Hamilton decomposition cannot be produced. We show that the '(n)=2 upper bound can be achieved for all even n. In particular, if n is a power of 2, Stn has a Hamilton decomposable spanning subgraph comprising more than half of the edges of Stn. Our results produce a better than twofold improvement on the known bounds for any kind of edge-disjoint Hamilton cycles in n-dimensional star graphs for general n.
- Computer Science