Hamiltonian Cycle and Path Embeddings ink-Aryn-Cubes Based on Structure Faults
Yali Lv, Cheng‐Kuan Lin, Jianxi Fan · The Computer Journal · 2016
The k-ary n-cube is one of the most attractive interconnection networks for parallel and distributed computing systems. In this paper, we investigate hamiltonian cycle and path embeddings in k-ary n-cubes Qnk based on structure faults, which means each faulty element is isomorphic to any connected subgraph of a connected graph. Let H be a connected graph with H∈{K1,K1,1,K1,2,K1,3}. We show that for two arbitrary distinct healthy nodes of a faulty Qnk, there exists a fault-free hamiltonian path connecting these two nodes if the number of faulty element is at most a certain number and each faulty element is isomorphic to a connected subgraph of H. We also show that there exists a fault-free hamiltonian cycle if the number of faulty element is at most a certain number and each faulty element is isomorphic to a connected subgraph of H. These results mean that the k-ary n-cube Qnk can tolerate up to 4(n−2) faulty nodes such that Qnk−V(F) is still hamiltonian and hamiltonian-connected, where F denotes the faulty set of Qnk.