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