TY - GEN
T1 - Conditional edge-fault-tolerant hamiltonian cycle embedding of star graphs
AU - Hsieh, Sun Yuan
AU - Wu, Chang De
AU - Huang, Chao Wen
PY - 2007/12/1
Y1 - 2007/12/1
N2 - The star graph has been recognized as an attractive alternative to the hypercube. In this paper, we investigate the hamiltoncity of a n-dimensional star graph. We show that for any n-dimensional star graph (n ≥ 4) with at most 3n - 10 faulty edges in which each node is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result improves the previously best known result where the number of tolerable faulty edges is bounded by 2n - 7. We also demonstrate that our result is optimal with respect to the worst case scenario where every other node of a six-length cycle is incident to exactly n - 3 faulty non-cycle edges.
AB - The star graph has been recognized as an attractive alternative to the hypercube. In this paper, we investigate the hamiltoncity of a n-dimensional star graph. We show that for any n-dimensional star graph (n ≥ 4) with at most 3n - 10 faulty edges in which each node is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result improves the previously best known result where the number of tolerable faulty edges is bounded by 2n - 7. We also demonstrate that our result is optimal with respect to the worst case scenario where every other node of a six-length cycle is incident to exactly n - 3 faulty non-cycle edges.
UR - http://www.scopus.com/inward/record.url?scp=48049111384&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=48049111384&partnerID=8YFLogxK
U2 - 10.1109/ICPADS.2007.4447776
DO - 10.1109/ICPADS.2007.4447776
M3 - Conference contribution
AN - SCOPUS:48049111384
SN - 9781424418909
T3 - Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS
BT - The 13th International Conference on Parallel and Distributed Systems, ICPADS
T2 - 13th International Conference on Parallel and Distributed Systems, ICPADS
Y2 - 5 December 2007 through 7 December 2007
ER -