Commenced in January 2007
Paper Count: 30123
Hamiltonian Related Properties with and without Faults of the Dual-Cube Interconnection Network and Their Variations
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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1124205Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 903
 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.
 M. Kobeissi and M. Mollard, “Disjoint cycles and spanning graphs of hypercubes”, Discrete Math., 288, 2004, no. 1-3, pp. 73–87.
 C.-H. Tsai, “Cycles embedding in hypercubes with node failures”, Inf. Process. Lett., 102, 2007, no. 6, pp. 242–246.
 P. Cull and S.M. Larson, “On generalized twisted cubes”, Inf. Process. Lett., 55, 1995, pp.53–55.
 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.
 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.
 C.-J. Lai and C.-H. Tsai, “On embedding cycles into faulty dual-cubes”, Inf. Process. Lett. , vol. 109, 2008, pp. 147–150.
 Y. Li, S. Peng, and W. Chu, “Efficient collective communications in dual-cube”, J. Supercomput., 28, 2004, pp.71–90.
 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.
 L.-H. Hsu and C.-K. Lin, Graph Theory and Interconnection Networks, CRC Press, Taylor and Francis Group, USA, 2009, ch. 1; ch. 9.
 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.
 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.
 J.-C. Chen and C.-H. Tsai, “Conditional edge-fault-tolerant hamiltonicity of dual-cubes”, Inf. Sci., 181, 2011, pp.620–627.
 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.
 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.
 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.
 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.
 A. Angjeli, E. Cheng, and L. Lipt´ak, “Linearly many faults in dual-cube-like networks”, Theor. Comput. Sci., 472, 2013, pp.1-8.