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 journalArticlepeer-review

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