We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Optimal fault-tolerant Hamiltonicity of star graphs with conditional edge faults.
- Authors
Hsieh, Sun-Yuan; Wu, Chang-De
- Abstract
The star graph is viewed as an attractive alternative to the hypercube. In this paper, we investigate the Hamiltonicity of an n-dimensional star graph. We show that for any n-dimensional star graph ( n≥4) with at most 3 n−10 faulty edges in which each node is incident with at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result improves on the previously best known result for the case where the number of tolerable faulty edges is bounded by 2 n−7. We also demonstrate that our result is optimal with respect to the worst case scenario, where every other node of a cycle of length 6 is incident with exactly n−3 faulty noncycle edges.
- Subjects
GRAPHIC methods; CHARTS, diagrams, etc.; HAMILTON spaces; DIFFERENTIAL geometry; HYPERCUBES
- Publication
Journal of Supercomputing, 2009, Vol 49, Issue 3, p354
- ISSN
0920-8542
- Publication type
Article
- DOI
10.1007/s11227-008-0242-9