Fault‐tolerant cycle embedding in hierarchical cubic networks

A hierarchical cubic network was proposed as an alternative to the hypercube. By HCN( n ), we denote the hierarchical cubic network that contains 2 n n ‐dimensional hypercubes. In this paper, using Gray codes, we construct fault‐free Hamiltonian cycles in an HCN( n ) with n − 1 link faults. Since the HCN( n ) is regular of degree n + 1, the result is optimal. We also construct longest fault‐free cycles of length 2 2 n − 1 in an HCN( n ) with a one‐node fault and fault‐free cycles of length at least 2 2 n − 2 f in an HCN( n ) with f ‐node faults, where 2 2 n is the number of nodes in the HCN( n ), f ≤ n − 1 if n = 3 or 4 and f ≤ n if n ≥ 5. Our results can be applied to the hierarchical folded‐hypercube network as well. © 2003 Wiley Periodicals, Inc.