Title :
On the embedding of edge-disjoint Hamiltonian cycles in transposition networks
Author :
Ruo-Wei Hung ; Hao-Yu Chih ; Chien-Hui Hou
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Chaoyang Univ. of Technol., Taichung, Taiwan
Abstract :
The presence of edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the network. Edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant hamiltonicity of an interconnection network. We will study the property of edge-disjoint Hamiltonian cycles in transposition networks in this article. The networks under study belong to a subclass of Cayley graphs whose generators are subsets of all possible transpositions. The transposition networks include other famous network topologies as their subgraphs, such as meshes, hypercubes, star graphs, and bubble-sort graphs. In this paper, we first introduce a novel decomposition of transposition networks. Using the proposed decomposition, we construct three edge-disjoint Hamiltonian cycles in 4-dimensional transposition network. We then show that n-dimensional transposition network with n ≥ 5 contains four edge-disjoint Hamiltonian cycles.
Keywords :
graph theory; group theory; network theory (graphs); 4-dimensional transposition network; Cayley graphs; edge-disjoint hamiltonian cycles; edge-fault tolerant hamiltonicity; interconnection network; n-dimensional transposition network; network topologies; Artificial neural networks; Hypercubes; Network topology; Routing; Structural rings; Topology; Edge-disjoint Hamiltonian cycles; edge-fault tolerant hamiltonicity; interconnection networks; transposition networks;
Conference_Titel :
Information Science, Electronics and Electrical Engineering (ISEEE), 2014 International Conference on
Conference_Location :
Sapporo
Print_ISBN :
978-1-4799-3196-5
DOI :
10.1109/InfoSEEE.2014.6948077