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

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.

Authors:

• Shih-Yan Chen
• Shin-Shin Kao

Keywords:

• Hypercubes
• dual-cubes
• fault-tolerant hamiltonian property
• dual-cube extensive networks
• dual-cube-like networks.

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.