{"title":"The Panpositionable Hamiltonicity of k-ary n-cubes","authors":"Chia-Jung Tsai, Shin-Shin Kao","volume":35,"journal":"International Journal of Mathematical and Computational Sciences","pagesStart":889,"pagesEnd":896,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/2528","abstract":"The hypercube Qn is one of the most well-known\r\nand popular interconnection networks and the k-ary n-cube Qk\r\nn is\r\nan enlarged family from Qn that keeps many pleasing properties\r\nfrom hypercubes. In this article, we study the panpositionable\r\nhamiltonicity of Qk\r\nn for k \u2265 3 and n \u2265 2. Let x, y of V (Qk\r\nn)\r\nbe two arbitrary vertices and C be a hamiltonian cycle of Qk\r\nn.\r\nWe use dC(x, y) to denote the distance between x and y on the\r\nhamiltonian cycle C. Define l as an integer satisfying d(x, y) \u2264 l \u2264 1\r\n2 |V (Qk\r\nn)|. We prove the followings:\r\n\u2022 When k = 3 and n \u2265 2, there exists a hamiltonian cycle C\r\nof Qk\r\nn such that dC(x, y) = l.\r\n\u2022 When k \u2265 5 is odd and n \u2265 2, we request that l \/\u2208 S\r\nwhere S is a set of specific integers. Then there exists a\r\nhamiltonian cycle C of Qk\r\nn such that dC(x, y) = l.\r\n\u2022 When k \u2265 4 is even and n \u2265 2, we request l-d(x, y) to be\r\neven. Then there exists a hamiltonian cycle C of Qk\r\nn such\r\nthat dC(x, y) = l.\r\nThe result is optimal since the restrictions on l is due to the\r\nstructure of Qk\r\nn by definition.","references":"[1] F. T. Leighton, Introduction to Parallel Algorithms and Architectures:\r\nArrays, Trees, Hypercubes. Morgan Kaufmann, 1992.\r\n[2] J.-S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Computing,\r\nVol. 29, pp. 821-832, 2003.\r\n[3] Y. A. Ashir and I. A. Stewart, On Embedding Cycles in k-ary n-cubes,\r\nParallel Processing Letters, Vol. 7, pp. 49-55, 1997.\r\n[4] S. Bettayeb, On the k-ary Hypercube, Theoretical Computer Science, Vol.\r\n140, pp. 333-339, 1995.\r\n[5] B. Bose, B. Broeg, Y. Kwon and Y. Ashir, Lee Distance and Topological\r\nProperties of k-ary n-cubes, IEEE Trans. Computers, Vol. 44, pp. 1021-\r\n1030, 1995.\r\n[6] I. A. Stewart and Y. Xiang. Bipanconnectivity and bipancyclicity in k-ary\r\nn-cubes, IEEE transactions on parallel and distributed systems. Vol. 20,\r\npp. 25-33, 2009.\r\n[7] S.-S. Kao, C.-K. Lin, H.-M. Huang and L.-H. Hsu, Panpositionable\r\nHamiltonian Graphs, Ars Combinatoria, Vol. 81, No.0, pp.209-223, 2006.\r\n[8] Y.-H. Teng, J. J. M. Tan and L.-H. Hsu, Panpositionable Hamiltonicity\r\nand panconnectivity of the arrangement graphs, Appl. Math. Comput.,\r\nVol.19. 414-432, 2008.\r\n[9] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-\r\nHolland, New York, 1980.\r\n[10] S. A. Wong, Hamiltonian cycles and paths in butterfly graphs, Networks,\r\nVol.26, pp.145-150, 1995.\r\n[11] C.-H. Huang, Strongly Hamiltonian laceability of the even k-ary n-cube,\r\nComput. Electr. Eng. (2009), doi:10.1016\/j.compeleceng.2009.01.002\r\n[12] D. Wang, T. An, M. Pan, K. Wang and S. Qu,Hamiltonian-like properies\r\nof k-Ary n-Cubes, in Proceedings of Sixth International Conference\r\non Parallel and Distributed Computing, Applications and Technologies\r\n(PDCAT05), pp. 1002-1007, 2005.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 35, 2009"}