ijfcsMarch2017revision.pdf (460.43 kB)
0/0

Optimal bounds for disjoint Hamilton cycles in star graphs

Download (460.43 kB)
journal contribution
posted on 27.06.2017 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.

History

School

  • Science

Department

  • Computer Science

Published in

International Journal of Foundations of Computer Science

Citation

DERAKHSHAN, P. and HUSSAK, W., 2017. Optimal bounds for disjoint Hamilton cycles in star graphs. International Journal of Foundations of Computer Science, 29 (3), pp.377–389.

Publisher

© World Scientific Publishing

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/

Acceptance date

06/05/2017

Publication date

2017

Notes

Electronic version of an article published as International Journal of Foundations of Computer Science, 29 (3), pp.377–389, doi: 10.1142/S0129054118500090 © World Scientific Publishing Company https://www.worldscientific.com/worldscinet/ijfcs

ISSN

1793-6373

Language

en

Exports

Logo branding

Exports