Conditional edge-fault-tolerant hamiltonian cycle embedding of star graphs

Sun Yuan Hsieh, Chang De Wu, Chao Wen Huang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

The star graph has been recognized as an attractive alternative to the hypercube. In this paper, we investigate the hamiltoncity of a n-dimensional star graph. We show that for any n-dimensional star graph (n ≥ 4) with at most 3n - 10 faulty edges in which each node is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result improves the previously best known result where the number of tolerable faulty edges is bounded by 2n - 7. We also demonstrate that our result is optimal with respect to the worst case scenario where every other node of a six-length cycle is incident to exactly n - 3 faulty non-cycle edges.

Original languageEnglish
Title of host publicationThe 13th International Conference on Parallel and Distributed Systems, ICPADS
DOIs
Publication statusPublished - 2007 Dec 1
Event13th International Conference on Parallel and Distributed Systems, ICPADS - Hsinchu, Taiwan
Duration: 2007 Dec 52007 Dec 7

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
Volume1
ISSN (Print)1521-9097

Other

Other13th International Conference on Parallel and Distributed Systems, ICPADS
CountryTaiwan
CityHsinchu
Period07-12-0507-12-07

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Conditional edge-fault-tolerant hamiltonian cycle embedding of star graphs'. Together they form a unique fingerprint.

Cite this