TY - GEN
T1 - Cycle embedding on the Möbius cube with both faulty nodes and faulty edges
AU - Hsieh, Sun Yuan
AU - Chang, Nai Wen
PY - 2005/9/1
Y1 - 2005/9/1
N2 - A graph G = (V, E) is said to be pancyclic if it contains fault-free cycles of all lengths from 4 to |V| in G. Let Fv and Fe be the sets of faulty nodes and faulty edges of an n-dimensional Möbius cube MQn, respectively, and let F = Fv ∪ Fe. In this paper, we show that MQn - F contains a fault-free Hamiltonian path when |F| ≤ n -1 and n ≥ 1. We also show that MQn -F is pancyclic when |F| ≤ n - 2 and n ≥ 2. Since MQn is regular of degree n, both results are optimal in the worst case.
AB - A graph G = (V, E) is said to be pancyclic if it contains fault-free cycles of all lengths from 4 to |V| in G. Let Fv and Fe be the sets of faulty nodes and faulty edges of an n-dimensional Möbius cube MQn, respectively, and let F = Fv ∪ Fe. In this paper, we show that MQn - F contains a fault-free Hamiltonian path when |F| ≤ n -1 and n ≥ 1. We also show that MQn -F is pancyclic when |F| ≤ n - 2 and n ≥ 2. Since MQn is regular of degree n, both results are optimal in the worst case.
UR - http://www.scopus.com/inward/record.url?scp=23944486716&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=23944486716&partnerID=8YFLogxK
U2 - 10.1109/ICPADS.2005.119
DO - 10.1109/ICPADS.2005.119
M3 - Conference contribution
AN - SCOPUS:23944486716
SN - 0769522815
T3 - Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS
SP - 620
EP - 624
BT - Proceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
A2 - Ma, J.
A2 - Yang, L.T.
T2 - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
Y2 - 20 July 2005 through 22 July 2005
ER -