Premium
Fault‐tolerant cycle embedding in hierarchical cubic networks
Author(s) -
Fu JungSheng,
Chen GenHuey
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10101
Subject(s) - hypercube , combinatorics , embedding , fault tolerance , node (physics) , mathematics , hamiltonian path , computer science , construct (python library) , discrete mathematics , distributed computing , physics , computer network , graph , quantum mechanics , artificial intelligence
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.