The Spanning Laceability of k-ary n-cubes when k is Even

Authors: Yuan-Kang Shih, Shu-Li Chang, Shin-Shin Kao

Abstract:

Qk n has been shown as an alternative to the hypercube family. For any even integer k ≥ 4 and any integer n ≥ 2, Qk n is a bipartite graph. In this paper, we will prove that given any pair of vertices, w and b, from different partite sets of Qk n, there exist 2n internally disjoint paths between w and b, denoted by {Pi | 0 ≤ i ≤ 2n-1}, such that 2n-1 i=0 Pi covers all vertices of Qk n. The result is optimal since each vertex of Qk n has exactly 2n neighbors.

Keywords: container, Hamiltonian, k-ary n-cube, m*-connected.

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

References:

[1] E. Anderson, J. Brooks, C. Grassl, and S. Scott, Performance of the Cray T3E Multiprocessor, in Proceedings of the 1997 ACM/IEEE conference on Supercomputing (SC-97), pp. 1-17, 1997.
[2] Y. Ashir, I. A. Stewart, and A. Ahmed, Communication Algorithms in k-ary n-cube Interconnection Networks, Information Processing Letters, Vol. 61, pp. 43-48, 1997.
[3] J.A. Bondy and U.S.R. Murty, Graph Theoery with applications, North- Holland, New York, 1980.
[4] S. Borkar, R. Cohen, G. Cox, S. Gleason, T. Gross, H.T. Kung, M. Lam, B. Moore, C. Peterson, J. Pieper, L. Rankin, P.S. Tseng, J. Sutton, J. Urbanski, and J. Webb, iWarp: An Integrated Solution to High-Speed Parallel Computing, in Proceedings of the 1988 ACM/IEEE conference on Supercomputing (SC-88), pp. 330-339, 1988.
[5] B. Bose, B. Broeg, Y. Kwon, and Y. Ashir, Lee Distance and Topological Properties of k-ary n-cubes, IEEE Transactions on Computers, Vol. 44, pp. 1021-1030, 1995.
[6] C.-H. Chang, C.-K. Lin, Jimmy J. M. Tan, H.-M. Huang, and L.-H. Hsu, The Super Spanning Connectivity and Super Spanning Laceability of the Enhanced Hypercubes, The Journal of Supercomputing, Vol. 48, pp. 66-87, 2009.
[7] C. Chin, T.-H. Weng, L.-H. Hsu, and S.-C. Chiou, The Spanning Connectivity of the Burnt Pancake Graphs, IEICE Transactions on Information and Systems, Vol. E92-D, pp. 389-400, 2009.
[8] K. Day and A. E. Al-Ayyoub, Fault Diameter of k-ary n-cube Networks, IEEE Transactions on Parallel and Distributed Systems, Vol. 8, pp. 903- 907, 1997.
[9] L.-H. Hsu and C.-K. Lin, Graph Theory and Interconnection Networks, CRC Press, Taylor & Francis Group, LLC, New York, 2008.
[10] C.-H. Huang, Strongly Hamiltonian Laceability of the Even k-ary ncube, Computers and Electrical Engineering, Vol. 35, pp. 659-663, 2009.
[11] R. E. Kessler and J. L. Schwarzmeier, CRAY T3D: A New Dimension for Cray Research, in Proceedings of 38th Internationl Computer Conference (COMPCON-93), pp. 176-182, 1993.
[12] C.-K. Lin, C.-P. Chang, T.-Y. Ho, Jimmy J. M. Tan, and L.-H. Hsu, A New Isomorphic Definition of the Crossed Cube and its Spanning Connectivity, Journal of Interconnection Networks, Vol. 10, pp. 149- 166, 2009.
[13] C.-K. Lin, H.-M. Huang, and L.-H. Hsu, On the Spanning Connectivity of Graphs, Discrete Mathematics, Vol. 307, pp. 285-289, 2007.
[14] C.-K. Lin, H.-M. Huang, Jimmy J. M. Tan, and L.-H. Hsu, On Spanning Connected Graphs, Discrete Mathematics, Vol. 308, pp. 1330-1333, 2008.
[15] C.-K. Lin, Jimmy J. M. Tan, and L.-H. Hsu, On the Spanning Connectively and Spanning Laceability of Hypercube-Like Networks, Theoretical Computer Science, Vol. 381, pp. 218-229, 2007.
[16] K. Menger, Zur allgemeinen Kurventheorie, Fundamenta Maththematicae, Vol. 10, pp. 95-115, 1927.
[17] M. D. Noakes, D. A. Wallach, and W. J. Dally, The J-Machine Multicomputer: An Architectural Evaluation, in Proceedings of the 20th Annual International Symposium on Computer Architecture (ISCA -93), pp. 224-235, 1993.
[18] O. Ore, Hamiltonian connected graphs, Journal de Math'ematiques Pures et Appliqu'ees, Vol. 42, pp. 21-27, 1963.
[19] I. A. Stewart and Y. Xiang, Embedding Long Paths in k-ary n-cubes with Faulty Nodes and Links, IEEE Transactions on Parallel and Distributed Systems, Vol. 19, pp. 1071-1085, 2008.
[20] I. A. Stewart and Y. Xiang, Bipanconnectivity and Bipancyclicity in kary n-cubes, IEEE Transactions on Parallel and Distributed Systems, Vol. 19, pp. 25-33, 2009.
[21] D. Wang, T. An, M. Pan, K. Wang, and S. Qu, Hamiltonian-Like Properties of k-ary n-cubes, in Proceedings of International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT-05), pp. 1002-1007, 2005.
[22] S. A. Wong, Hammiltonian Cycles and Paths in Butterfly Graphs, Networks, Vol. 26, pp. 145-150, 1995.
[23] M.-C. Yang, Jimmy J. M. Tan, and L.-H. Hsu, Hamiltonian Circuit and Linear Array Embeddings in Faulty k-ary n-cubes, Journal of Parallel and Distributed Computing, Vol. 67, pp. 362-368, 2007.