Fault‐tolerant cycle embedding in hierarchical cubic networks
Jung‐Sheng Fu, Gen-Huey Chen · Networks · 2003
Abstract A hierarchical cubic network was proposed as an alternative to the hypercube. By HCN(n), we denote the hierarchical cubic network that contains 2nn‐dimensional hypercubes. In this paper, using Gray codes, we construct fault‐free Hamiltonian cycles in an HCN(n) withn− 1 link faults. Since the HCN(n) is regular of degreen+ 1, the result is optimal. We also construct longest fault‐free cycles of length 22n− 1 in an HCN(n) with a one‐node fault and fault‐free cycles of length at least 22n− 2fin an HCN(n) withf‐node faults, where 22nis the number of nodes in the HCN(n),f≤n− 1 ifn= 3 or 4 andf≤nifn≥ 5. Our results can be applied to the hierarchical folded‐hypercube network as well. © 2003 Wiley Periodicals, Inc.