Hamiltonian cycle and path embeddings in 3-ary n-cubes based on K1,3-structure faults

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 (Q(n)(3) based on K-1,K-3-structure faults, which means each faulty element is isomorphic to any connected subgraph of a connected graph K-1,K-3. We show that for two arbitrary distinct healthy nodes of a faulty Q(n)(3), 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 K-1,K-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 K-1,K-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 Q(n)(3) can tolerate up to 4(n - 2) faulty nodes such that Q(n)(3) - V(F) is still hamiltonian and hamiltonian-connected, where F denotes the faulty set of CV. (C) 2018 Elsevier Inc. All rights reserved.