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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

6 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)148-158
Journal / PublicationJournal of Parallel and Distributed Computing
Volume120
Online published21 Jun 2018
Publication statusPublished - Oct 2018

Abstract

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 − 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 Qn3V(F) is still hamiltonian and hamiltonian-connected, where F denotes the faulty set of Qn3.

Research Area(s)

  • 3-ary n-cube, Hamiltonian cycle, Hamiltonian path, Interconnection network, Structure fault