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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1585,
author = {Shiying Wang and Shurong Zhang},
title = {Embeddings of hamiltonian paths in faulty k-ary 2-cubes},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {47-61},
zbl = {1255.05183},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1585}
}
Shiying Wang; Shurong Zhang. Embeddings of hamiltonian paths in faulty k-ary 2-cubes. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 47-61. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1585/
[000] [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.
[001] [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. | Zbl 1209.68375
[002] [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. | Zbl 1149.68409
[003] [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.
[004] [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. | Zbl 1207.05106
[005] [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.
[006] [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.
[007] [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.
[008] [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.
[009] [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. | Zbl 1161.68684
[010] [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.
[011] [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.
[012] [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.
[013] [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. | Zbl 1185.05091
[014] [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.
[015] [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. | Zbl 1072.68082
[016] [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. | Zbl 1183.68093
[017] [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. | Zbl 1163.68314
[018] [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. | Zbl 1115.68032