We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Optimal Bounds for Disjoint Hamilton Cycles in Star Graphs.
- Authors
Derakhshan, Parisa; Hussak, Walter
- Abstract
In interconnection network topologies, the -dimensional star graph has vertices corresponding to permutations of symbols and edges which exchange the positions of the first symbol with any one of the other symbols. The star graph compares favorably with the familiar -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 has been to label the edges in a certain way and then take images of a known base 2-labelled Hamilton cycle under different 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 other than for the case of which does provide a Hamilton decomposition. In this paper we show that, for all n, not more than , where is Euler's totient function, edge-disjoint Hamilton cycles can be produced by such automorphisms. Thus, for non-prime , a Hamilton decomposition cannot be produced. We show that the upper bound can be achieved for all even . In particular, if is a power of 2, has a Hamilton decomposable spanning subgraph comprising more than half of the edges of . Our results produce a better than twofold improvement on the known bounds for any kind of edge-disjoint Hamilton cycles in -dimensional star graphs for general .
- Subjects
STAR graphs (Graph theory); PATHS &; cycles in graph theory; TOPOLOGY; HAMILTON spaces; MATHEMATICAL bounds; AUTOMORPHISMS
- Publication
International Journal of Foundations of Computer Science, 2018, Vol 29, Issue 3, p377
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054118500090