Discussiones Mathematicae Graph Theory 32(1) (2012) 47-61
doi: 10.7151/dmgt.1585

[BIBTex] [PDF] [PS]

Embeddings of Hamiltonian Paths in Faulty k-ary 2-cubes

Shiying Wang and Shurong Zhang

School of Mathematical Sciences
Shanxi University, Taiyuan, Shanxi 030006
Peoples Republic of China

Abstract

It is well known that the k-ary n-cube has been one of the most efficient interconnection networks for distributed-memory parallel systems. A k-ary n-cube is bipartite if and only if k is even. Let (X,Y) be a bipartition of a k-ary 2-cube (even integer k ≥ 4). In this paper, we prove that for any two healthy vertices u ∈ X, v ∈ Y, there exists a hamiltonian path from u to v in the faulty k-ary 2-cube with one faulty vertex in each part.

Keywords: complex networks, path embeddings, fault-tolerance, k-ary n-cubes

2010 Mathematics Subject Classification: Primary: 05C82, 05C60; Secondary: 68R10, 94C15.

References

[1]Y.A. Ashir and I.A. Stewart, Fault-tolerant embeddings of hamiltonian circuits in k-ary n-cubes, SIAM J. Discrete Math. 15 (2002) 317--328, doi: 10.1137/S0895480196311183.
[2]S.-Y. Hsieh and Y.-R. Cian, Conditional edge-fault hamiltonicity of augmented cubes, Inform. Sciences 180 (2010) 2596--2617, doi: 10.1016/j.ins.2010.03.005.
[3]S.-Y. Hsieh and C.-N. Kuo, Hamilton-connectivity and strongly Hamiltonian-laceability of folded hypercubes, Comput. Math. Appl. 53 (2007) 1040--1044, doi: 10.1016/j.camwa.2006.10.033.
[4]S.-Y. Hsieh and C.-W. Lee, Conditional edge-fault hamiltonicity of matching composition networks, IEEE Trans. Parallel Distrib. Syst. 20 (2009) 581--592, doi: 10.1109/TPDS.2008.123.
[5]S.-Y. Hsieh and C.-W. Lee, Pancyclicity of restricted hypercube-like networks under the conditional fault model, SIAM J. Discrete Math. 23 (2010) 2100--2119, doi: 10.1137/090753747.
[6]S.-Y. Hsieh and C.-D. Wu, Optimal fault-tolerant hamiltonicity of star graphs with conditional edge faults, J. Supercomput. 49 (2009) 354--372, doi: 10.1007/s11227-008-0242-9.
[7]T.-L. Kueng, C.-K. Lin, T. Liang, J.J.M. Tan and Lih-Hsing Hsu, Embedding paths of variable lengths into hypercubes with conditional link-faults, Parallel Comput. 35 (2009) 441--454, doi: 10.1016/j.parco.2009.06.002.
[8]H.-C. Kim and J.-H. Park Fault hamiltonicity of two-dimensional torus networks, Proceedings of Workshop on Algorithms and Computation WAAC'00, Tokyo, Japan, (2000), 110--117.
[9]R.E. Kessler and J.L. Schwarzmeier, Cray T3D: a new dimension for Cray Research, Proceedings of the 38th IEEE Computer Society International Conference, Compcon Spring'93, San Francisco, CA (1993), 176--182.
[10]T.-K. Li, C.-H. Tsai, J.J.M. Tan and L.-H. Hsu, Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes, Inform. Process. Lett. 87 (2003) 107--110, doi: 10.1016/S0020-0190(03)00258-8.
[11]M. Noakes and W.J. Dally, System design of the J-machine, Proceedings of the sixth MIT Conference on Advanced Research in VLSI, (MIT Press, Cambridge, MA, 1990) 179--194.
[12]C. Peterson, J. Sutton and P. Wiley, iWarp: a 100-MOPS, LIW microprocessor for multicomputers, IEEE Micro 11(3)(1991) 26--29, 81-87, doi: 10.1109/40.87568.
[13]Y. Rouskov, S. Latifi and P.K. Srimani, Conditional fault diameter of star graph networks, J. Parallel Distr. Com. 33 (1996) 91--97, doi: 10.1006/jpdc.1996.0028.
[14]L.-M. Shih, J.J.M. Tan and L.-H. Hsu, Edge-bipancyclicity of conditional faulty hypercubes, Inform. Process. Lett. 105 (2007) 20--25, doi: 10.1016/j.ipl.2007.07.009.
[15]I.A. Stewart and Y. Xiang, Embedding long paths in k-ary n-cubes with faulty nodes and links, IEEE Trans. Parallel Distrib. Syst. 19 (2008) 1071--1085, doi: 10.1109/TPDS.2007.70787.
[16]C.-H. Tsai, Linear array and ring embeddings in conditional faulty hypercubes, Theor. Comput. Sci. 314 (2004) 431--443, doi: 10.1016/j.tcs.2004.01.035.
[17]S. Wang and S. Lin, Path embeddings in faulty 3-ary n-cubes, Inform. Sciences 180 (2010) 191--197, doi: 10.1016/j.ins.2009.09.007.
[18]H.-L. Wang, J.-W. Wang and J.-M. Xu, Edge-fault-tolerant bipanconnectivity of hypercubes, Inform. Sciences 179 (2009) 404--409, doi: 10.1016/j.ins.2008.10.011.
[19]M.-C. Yang, J.J.M. Tan and L.-H. Hsu, Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes, J. Parallel Distr. Com. 67 (2007) 362--368, doi: 10.1016/j.jpdc.2005.10.004.

Received 31 May 2010
Revised 22 January 2011
Accepted 24 January 2011