Longest fault-free paths in star graphs with vertex faults

Sun Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Research output: Contribution to journalArticlepeer-review

49 Scopus citations

Abstract

The star graph Sn has been recognized as an attractive alternative to the hypercube. Since S1, S2, and S3 have trivial structures, we focus our attention on Sn with n ≥ 4 in this paper. Let Fv denote the set of faulty vertices in Sn. We show that when |Fv| ≤ n - 5 ,Sn with n ≥ 6 contains a fault-free path of length n! - 2|Fv| - 2 (n! - 2 |Fv| - 1) between arbitrary two vertices of even (odd) distance. Since Sn is bipartite with two partite sets of equal size, the path is longest for the worst-case scenario. The situation of n ≥ 4 and |Fv| ≥ n - 5 is also discussed.

Original languageEnglish
Pages (from-to)215-227
Number of pages13
JournalTheoretical Computer Science
Volume262
Issue number1-2
DOIs
StatePublished - 2001

Keywords

  • Bipartite graph
  • Cayley graph
  • Fault-tolerant embedding
  • Graph-theoretic interconnection network
  • Hamiltonian path
  • Longest path
  • Star graph

Fingerprint

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

Cite this