Node‐disjoint paths and related problems on hierarchical cubic networks

An n ‐dimensional hierarchical cubic network [denoted by HCN( n )] contains 2 n n ‐dimensional hypercubes. The diameter of the HCN( n ), which is equal to n + ⌊( n + 1)/3⌋ + 1, is about two‐thirds the diameter of a comparable hypercube, even though it uses about half as many links per node. In this paper, a maximal number of node‐disjoint paths are constructed between every two distinct nodes of the HCN( n ). Their maximal length is bounded above by n + ⌊ n /3⌋ + 4, which is nearly optimal. The ( n + 1)‐wide diameter and n ‐fault diameter of the HCN( n ) are shown to be n + ⌊ n /3⌋ + 3 or n + ⌊ n /3⌋ + 4, which are about two‐thirds those of a comparable hypercube. Our results reveal that the HCN( n ) has a smaller wide diameter and fault diameter than those of a comparable hypercube. © 2002 Wiley Periodicals, Inc.