Longest fault-free paths in star graphs with edge faults

Sun Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Research output: Contribution to journalArticlepeer-review

58 Scopus citations

Abstract

In this paper, we aim to embed longest fault-free paths in an n-dimensional star graph with edge faults. When n ≥ 6 and there are n - 3 edge faults, a longest fault-free path can be embedded between two arbitrary distinct vertices, exclusive of two exceptions in which at most two vertices are excluded. Since the star graph is regular of degree n - 1, n - 3 (edge faults) is maximal in the worst case. When n ≥ 6 and there are n - 4 edge faults, a longest fault-free path can be embedded between two arbitrary distinct vertices. The situation of n < 6 is also discussed.

Original languageEnglish
Pages (from-to)960-971
Number of pages12
JournalIEEE Transactions on Computers
Volume50
Issue number9
DOIs
StatePublished - Sep 2001

Keywords

  • Bipartite graph
  • Embedding
  • Fault tolerance
  • Hamiltonicity
  • Longest path
  • Star graph

Fingerprint

Dive into the research topics of 'Longest fault-free paths in star graphs with edge faults'. Together they form a unique fingerprint.

Cite this