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: dual-cubes, dual-cube extensive networks, dual-cube-like networks, hypercubes, fault-tolerant hamiltonian property