A Systematic Approach for Finding Hamiltonian Cycles with a Prescribed Edge in Crossed Cubes

Authors: Jheng-Cheng Chen, Chia-Jui Lai, Chang-Hsiung Tsai,

Abstract:

The crossed cube is one of the most notable variations of hypercube, but some properties of the former are superior to those of the latter. For example, the diameter of the crossed cube is almost the half of that of the hypercube. In this paper, we focus on the problem embedding a Hamiltonian cycle through an arbitrary given edge in the crossed cube. We give necessary and sufficient condition for determining whether a given permutation with n elements over Zn generates a Hamiltonian cycle pattern of the crossed cube. Moreover, we obtain a lower bound for the number of different Hamiltonian cycles passing through a given edge in an n-dimensional crossed cube. Our work extends some recently obtained results.

Keywords: Interconnection network, Hamiltonian, crossed cubes, prescribed edge.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330443

References:

[1] E. Abuelrub and S. Bettayeb, "Embedding Rings into Faulty Twisted Hypercubes," Computers and Artificial Intelligence, vol. 16, pp. 425-441, 1997.
[2] S. G. Akl,, Parallel Computation: Models and Methods, Upper Saddle River, NJ: Prentice-Hall, 1997.
[3] K. Efe,"The Crossed Cube Architecture for Parallel Computing," IEEE Trans. Parallel and Distributed Systems, vol. 3, no. 5, pp. 513-524, 1992.
[4] K. Efe, P. K. Blackwell, W. Slough, and T. Shiau, "Topological Properties of the Crossed Cube Architecture," Parallel Computing, vol. 20, pp. 1763- 1775, 1994.
[5] J. Fan, X. Lin, and X. Jia, "Node-pancyclicity and edge-pancyclicity of Crossed cubes," Information Processing Letters, vol. 93, pp. 133-138, 2005.
[6] J. P. Hayes and T. N. Mudge, "Hypercube supercomputer," Proc. IEEE, vol. 17, pp. 1829-1841, 1989.
[7] W. T. Huang, Y. C. Chuang, J. M. Tan, and L. H. Hsu, "On the Fault-Tolerant Hamiltonicity of Faulty Crossed Cubes," IEICE Trans. Fundamentals, vol. E85-A, no. 6, pp. 1359-1370, 2002.
[8] H. S. Hung, J. S. Fu, and G. H. Chen, "Fault-free Hamiltonian cycles in Crossed Cubes with Conditional Link Faults," Information Sciences, vol. 177, pp. 5664-5674, 2007.
[9] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: arrays, trees, hypercubes. San Mateo: Morgan Kaufman, 1992.
[10] SGI, Origin2000 Rackmount Ower-s Guide, 007-3456-003, http://techpubs.sgi.com/, 1997.
[11] L. W. Tucker and G. G. Robertson, "Architecture and applications of the connection machine," IEEE Computer, vol. 21, pp. 26-38, 1988.
[12] D. Wang,"On Embedding Hamiltonian Cycles in Crossed Cubes," IEEE Trans. Parallel and Distributed Systems, vol. 19, no. 3, pp. 334-346, 2008.
[13] M. C. Yang, T. K. Li, J. M. Tan, and L. H. Hsu, "Fault-tolerant Cycleembedding of Crossed Cubes," Information Processing Letters, vol. 88, pp. 149-154, 2003.
[14] S. Q. Zheng and S. Latifi, "Optimal Simulation of Linear Multiprocessor Architectures on Multiply-Twisted Cube Using Generalized Gray Code," IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 6, pp. 612-619, 1996.