ijfcsMarch2017revision.pdf (460.43 kB)
Optimal bounds for disjoint Hamilton cycles in star graphs
journal contribution
posted on 2017-06-27, 13:14 authored by Parisa Derakhshan, Walter HussakWalter HussakIn 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 ScienceCitation
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 PublishingVersion
- 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
2017-05-06Publication date
2017Notes
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/ijfcsISSN
1793-6373Publisher version
Language
- en