Longest Fault-Free Paths in Star Graphs with Edge Faults.
Journal
IEEE Trans. Computers
Journal Volume
50
Journal Issue
9
Pages
960-971
Date Issued
2001
Author(s)
Abstract
In this paper, we aim to embed longest fault-free paths in an n-dimensional star graph with edge faults. When n/spl ges/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/spl ges/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.
Type
journal article