On container length and connectivity in unidirectional hypercubes
Jung‐Sing Jwo, Tai-Ching Tuan · Networks · 1998
In this paper, we show that the two unidirectional binary n-cubes, namely, Q1(n) and Q2(n), proposed as high-speed networking schemes by Chou and Du are maximum fault-tolerant, that is, from vertex a to vertex b in the network, we can determine a set of ζ(a, b) vertex-disjoint routing paths, where ζ(a, b) = ⌈n/2⌉, if a has even parity and b has odd parity and ⌊n/2⌋ otherwise. Furthermore, the container problem as defined by Hsu for the two maximum fault-tolerant, unidirectional topologies is studied. In particular, we show that the smallest possible length for any maximum fault-tolerant container from a to b is at most (1) ℓ + 4, where ℓ is the shortest path length in Q1(n) from a to b, and (2) ℓ + 5, where ℓ is the shortest path length in Q2(n) (n is odd) (i) from a to b when a and b have the same leading-bit values and (ii) from a to b′ (b′ and b only differ at leading-bit positions) when otherwise. © 1998 John Wiley & Sons, Inc. Networks 32: 307–317, 1998