The Wide Diameter of Folded Hypercube
Hongmei Liu · 2010
The n-dimensional Folded hypercube FQnis a very popular topological structure of multi-computer networks because of many excellent features. But further exploring of its properties regarding robustness are needed to establish sound foundation of its applications to important networks requiring high reliability. In this paper, the one-to-one parallel routes in FQnfor n ≥ 2 are concerned. For any two distinct nodes with Hamming distance r, the n + 1 internal vertex-disjoint paths joining these two nodes have been constructed. Meanwhile it is found that there are r paths of length r and n + 1 - r paths of length r + 2 when 1 ≤ r ≤ [n/2], or r paths of length n - r + 3 and n - r + 1 paths of length n - r + 1 when [n/2]nis no more than [n/2] + 2. The n + 1 internal vertex-disjoint paths form an n + 1-container of FQn, which implies that the fault-tolerant diameter is no more than [n/2] + 2. These properties show that interconnection networks modeled by FQnare extremely robust. They have very good fault tolerance and reliability as a topological structure of multi-computer network.