TY - JOUR
T1 - Hamiltonian cycle and path embeddings in 3-ary n-cubes based on K1,3-structure faults
AU - Lv, Yali
AU - Lin, Cheng-Kuan
AU - Fan, Jianxi
AU - Jia, Xiaohua
PY - 2018/10
Y1 - 2018/10
N2 - 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 Qn3 based on K1,3-structure faults, which means each faulty element is isomorphic to any connected subgraph of a connected graph K1,3. 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 any connected subgraph of K1,3. 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 any connected subgraph of K1,3. Then, we provide the simulation experiment to find a hamiltonian cycle and a hamiltonian path in structure faulty 3-ary n-cubes and verify the theoretical results. These results mean that the 3-ary n-cube Qn3 can tolerate up to 4(n−2) faulty nodes such that Qn3−V(F) is still hamiltonian and hamiltonian-connected, where F denotes the faulty set of Qn3.
AB - 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 Qn3 based on K1,3-structure faults, which means each faulty element is isomorphic to any connected subgraph of a connected graph K1,3. 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 any connected subgraph of K1,3. 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 any connected subgraph of K1,3. Then, we provide the simulation experiment to find a hamiltonian cycle and a hamiltonian path in structure faulty 3-ary n-cubes and verify the theoretical results. These results mean that the 3-ary n-cube Qn3 can tolerate up to 4(n−2) faulty nodes such that Qn3−V(F) is still hamiltonian and hamiltonian-connected, where F denotes the faulty set of Qn3.
KW - 3-ary n-cube
KW - Hamiltonian cycle
KW - Hamiltonian path
KW - Interconnection network
KW - Structure fault
UR - http://www.scopus.com/inward/record.url?scp=85049353347&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85049353347&origin=recordpage
U2 - 10.1016/j.jpdc.2018.06.007
DO - 10.1016/j.jpdc.2018.06.007
M3 - 21_Publication in refereed journal
VL - 120
SP - 148
EP - 158
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
SN - 0743-7315
ER -