The Panpositionable Hamiltonicity of k-ary n-cubes

Authors: Chia-Jung Tsai, Shin-Shin Kao

Abstract:

The hypercube Qn is one of the most well-known and popular interconnection networks and the k-ary n-cube Qk n is an enlarged family from Qn that keeps many pleasing properties from hypercubes. In this article, we study the panpositionable hamiltonicity of Qk n for k ≥ 3 and n ≥ 2. Let x, y of V (Qk n) be two arbitrary vertices and C be a hamiltonian cycle of Qk n. We use dC(x, y) to denote the distance between x and y on the hamiltonian cycle C. Define l as an integer satisfying d(x, y) ≤ l ≤ 1 2 |V (Qk n)|. We prove the followings: • When k = 3 and n ≥ 2, there exists a hamiltonian cycle C of Qk n such that dC(x, y) = l. • When k ≥ 5 is odd and n ≥ 2, we request that l /∈ S where S is a set of specific integers. Then there exists a hamiltonian cycle C of Qk n such that dC(x, y) = l. • When k ≥ 4 is even and n ≥ 2, we request l-d(x, y) to be even. Then there exists a hamiltonian cycle C of Qk n such that dC(x, y) = l. The result is optimal since the restrictions on l is due to the structure of Qk n by definition.

Keywords: Hamiltonian, panpositionable, bipanpositionable, k-ary n-cube.

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

References:

[1] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, 1992.
[2] J.-S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Computing, Vol. 29, pp. 821-832, 2003.
[3] Y. A. Ashir and I. A. Stewart, On Embedding Cycles in k-ary n-cubes, Parallel Processing Letters, Vol. 7, pp. 49-55, 1997.
[4] S. Bettayeb, On the k-ary Hypercube, Theoretical Computer Science, Vol. 140, pp. 333-339, 1995.
[5] B. Bose, B. Broeg, Y. Kwon and Y. Ashir, Lee Distance and Topological Properties of k-ary n-cubes, IEEE Trans. Computers, Vol. 44, pp. 1021- 1030, 1995.
[6] I. A. Stewart and Y. Xiang. Bipanconnectivity and bipancyclicity in k-ary n-cubes, IEEE transactions on parallel and distributed systems. Vol. 20, pp. 25-33, 2009.
[7] S.-S. Kao, C.-K. Lin, H.-M. Huang and L.-H. Hsu, Panpositionable Hamiltonian Graphs, Ars Combinatoria, Vol. 81, No.0, pp.209-223, 2006.
[8] Y.-H. Teng, J. J. M. Tan and L.-H. Hsu, Panpositionable Hamiltonicity and panconnectivity of the arrangement graphs, Appl. Math. Comput., Vol.19. 414-432, 2008.
[9] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North- Holland, New York, 1980.
[10] S. A. Wong, Hamiltonian cycles and paths in butterfly graphs, Networks, Vol.26, pp.145-150, 1995.
[11] C.-H. Huang, Strongly Hamiltonian laceability of the even k-ary n-cube, Comput. Electr. Eng. (2009), doi:10.1016/j.compeleceng.2009.01.002
[12] D. Wang, T. An, M. Pan, K. Wang and S. Qu,Hamiltonian-like properies of k-Ary n-Cubes, in Proceedings of Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT05), pp. 1002-1007, 2005.