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 language | English |
---|---|
Pages (from-to) | 960-971 |
Number of pages | 12 |
Journal | IEEE Transactions on Computers |
Volume | 50 |
Issue number | 9 |
DOIs | |
Publication status | Published - 2001 Sept |
All Science Journal Classification (ASJC) codes
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics