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

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.

Authors:

• Yuan-Kang Shih
• Shu-Li Chang
• Shin-Shin Kao

Keywords:

• container
• Hamiltonian
• k-ary n-cube
• m*-connected.

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.