The Wide Diameter of Folded Hypercube

摘要

The n-dimensional Folded hypercube FQn is 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 FQn for 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+l-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+l when [n/2] < r ≤n. These results conclude that the n + 1-wide diameter of FQn is 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 FQn are extremely robust. They have very good fault tolerance and reliability as a topological structure of multi-computer network.