Conditional edge-fault hamiltonicity of matching composition networks

Sun Yuan Hsieh, Chia Wei Lee

Research output: Contribution to journalArticlepeer-review

56 Citations (Scopus)

Abstract

A graph G is called Hamiltonian if there is a Hamiltonian cycle in G. The conditional edge-fault Hamiltonicity of a Hamiltonian graph G is the largest k such that after removing k faulty edges from G, provided that each node is incident to at least two fault-free edges, the resulting graph contains a Hamiltonian cycle. In this paper, we sketch common properties of a class of networks, called Matching Composition Networks (MCNs), such that the conditional edge-fault Hamiltonicity of MCNs can be determined from the found properties. We then apply our technical theorems to determine conditional edge-fault Hamiltonicities of several multiprocessor systems, including n-dimensional crossed cubes, n-dimensional twisted cubes, n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, and n-dimensional hyper Petersen networks. Moreover, we also demonstrate that our technical theorems can be applied to network construction.

Original languageEnglish
Pages (from-to)581-592
Number of pages12
JournalIEEE Transactions on Parallel and Distributed Systems
Volume20
Issue number4
DOIs
Publication statusPublished - 2009 Feb 10

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Conditional edge-fault hamiltonicity of matching composition networks'. Together they form a unique fingerprint.

Cite this