Hamiltonian Related Properties with and without Faults of the Dual-Cube Interconnection Network and Their Variations

Authors: Shih-Yan Chen, Shin-Shin Kao

Abstract:

In this paper, a thorough review about dual-cubes, DCn, the related studies and their variations are given. DCn was introduced to be a network which retains the pleasing properties of hypercube Qn but has a much smaller diameter. In fact, it is so constructed that the number of vertices of DCn is equal to the number of vertices of Q2n +1. However, each vertex in DCn is adjacent to n + 1 neighbors and so DCn has (n + 1) × 2^2n edges in total, which is roughly half the number of edges of Q2n+1. In addition, the diameter of any DCn is 2n +2, which is of the same order of that of Q2n+1. For selfcompleteness, basic definitions, construction rules and symbols are provided. We chronicle the results, where eleven significant theorems are presented, and include some open problems at the end.

Keywords: Hypercubes, dual-cubes, fault-tolerant hamiltonian property, dual-cube extensive networks, dual-cube-like networks.

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

References:

[1] F. Harary, J. P. Hayes, and H.-J. Wu, “A survey of the theory of the hypercube graphs”, Comput. Math. Appl., 15, 1988, no. 4, pp. 277–289.
[2] M. Kobeissi and M. Mollard, “Disjoint cycles and spanning graphs of hypercubes”, Discrete Math., 288, 2004, no. 1-3, pp. 73–87.
[3] C.-H. Tsai, “Cycles embedding in hypercubes with node failures”, Inf. Process. Lett., 102, 2007, no. 6, pp. 242–246.
[4] P. Cull and S.M. Larson, “On generalized twisted cubes”, Inf. Process. Lett., 55, 1995, pp.53–55.
[5] Y. Li and S. Peng, “Dual-cubes: a new interconnection network for high-performance computer clusters”, Proceedings of the 2000 International Computer Symposium, Workshop on Computer Architecture. Chia-Yi, Taiwan, Dec. 2000, 51–57.
[6] Z. Jiang and J. Wu, “A limited-global information model for fault-tolerant routing in dual-cube”, Int. J. Parallel Emergent and Distrib. Syst., 21, 2006, no. 1, pp.61–77.
[7] C.-J. Lai and C.-H. Tsai, “On embedding cycles into faulty dual-cubes”, Inf. Process. Lett. , vol. 109, 2008, pp. 147–150.
[8] Y. Li, S. Peng, and W. Chu, “Efficient collective communications in dual-cube”, J. Supercomput., 28, 2004, pp.71–90.
[9] Y. Li, S. Peng, and W. Chu, “Fault tolerant cycle embedding dual-cube with node faults”, Int. J. High Performance Computing and Networking, 3, 2005, no. 1, pp.45–53.
[10] L.-H. Hsu and C.-K. Lin, Graph Theory and Interconnection Networks, CRC Press, Taylor and Francis Group, USA, 2009, ch. 1; ch. 9.
[11] Y. Li, S. Peng, and W. Chu, “Hamiltonian cycle embedding for fault tolerance in dual-cube”, Proceedings of the IASTED International Conference on Networks, Parallel and Distributing Processing, and Applications, 2002, pp. 1–6.
[12] Y.-K. Shih, H.-C. Chuang, S.-S. Kao and J. J.-M. Tan, “Mutually independent hamiltonian cycles in Dual-cubes”, J. Supercomput., 54, 2010, pp. 239–251.
[13] J.-C. Chen and C.-H. Tsai, “Conditional edge-fault-tolerant hamiltonicity of dual-cubes”, Inf. Sci., 181, 2011, pp.620–627.
[14] Y.A. Ashir and I.A. Stewart, “Fault-tolerant embedding of Hamiltonian circuits in k-ary n-cube”, SIAM Journal on Discrete Mathematics, 15(3), 2002, pp. 317–328.
[15] M.Y. Chan and S.-J. Lee, “On the existence of hamiltonian circuits in faulty hypercubes”, SIAM Journal on Discrete Mathematics, 4(4), 1991, pp.511-527.
[16] P.K. Jha, “1-Perfect codes over dual-cubes vis-`a-vis hamming codes over hypercubes”, IEEE Trans. Inf. Theory, 61, no. 8, 2015, pp. 4259–4268.
[17] S.-Y. Chen and S.-S. Kao, “Hamiltonian connectivity and globally 3*-connected of Dual-cube Extensive Networks”, Comput. Electr. Eng., 36, 2010, pp. 404-413.
[18] A. Angjeli, E. Cheng, and L. Lipt´ak, “Linearly many faults in dual-cube-like networks”, Theor. Comput. Sci., 472, 2013, pp.1-8.