Fault-tolerant ring embedding in a star graph with both link and node failures

Yu-Chee Tseng*, Shu Hui Chang, Jang Ping Sheu

*Corresponding author for this work

Research output: Contribution to journalArticle

107 Scopus citations


The star graph interconnection network has been recognized as an attractive alternative to the hypercube network. Previously, the star graph has been shown to contain a Hamiltonian cycle. In this paper, we consider an injured star graph with some faulty links and nodes. We show that even with f e ≤ n - 3 faulty links, a Hamiltonian cycle still can be found in an n-star, and that with f v ≤ n - 3 faulty nodes, a ring containing at most 4f v nodes less than that in a Hamiltonian cycle can be found (i.e., the ring contains at least n! - 4f v nodes). In general, in an n-star with f e faulty links and f v faulty nodes, where f e + f v ≤ n - 3, our embedding is able to establish a ring containing at least n! - 4f v nodes.

Original languageEnglish
Pages (from-to)1185-1195
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number12
StatePublished - 1 Dec 1997


  • Fault tolerance
  • Graph embedding
  • Hamiltonian cycle
  • Interconnection network
  • Processor allocation
  • Ring
  • Star graph

Fingerprint Dive into the research topics of 'Fault-tolerant ring embedding in a star graph with both link and node failures'. Together they form a unique fingerprint.

  • Cite this