容錯性一直是連結網路中的一個重要的課題，其內容主要是討論在圖(graph) 中，若是點與邊發生錯誤，當網路失去連通性的情況下，一些主要圖形性質的相關研究。如果一個圖包含所有長度從4到 的圓圈(cycle)，那麼我們說這一個圖具有全圓性的特性(pancyclic)。令 和 分別代表在圖中錯點和錯邊的集合。在本篇論文中，我們證明了在 維度的莫氏立方體(Möbius cube)中，即使最多有 個錯誤(共包含錯點和錯邊)的情況下，莫氏立方體仍然保有全圓性的特性。

　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 U 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.

[1] J. C. Bermond, Ed., “Interconnection Networks,” a special issue of Discrete Applied Mathematics, vol. 37+38, 1992.

[2] J. Bruck, R. Cypher, and C. T. Ho, “Fault-tolerant meshes and hypercubes with minimal numbers of spares,” IEEE Transaction on Computers, vol. 42, no. 9, pp. 1089–1104, 1993.

[3] J. Bruck, R. Cypher, and C. T. Ho, “Fault-tolerant de Bruijn and shuffle-exchange networks,” IEEE Transaction on Parallel and Distributed Systems, vol. 5, no. 5, pp. 548–553, 1994.

[4] J. Bruck, R. Cypher, and C. T. Ho, “On the construction of fault-tolerant cubeconnected cycles networks,” Journal of Parallel and Distributed Computing, vol. 25, issue 1, pp. 98–106, 1995.

[5] J. Bruck, R. Cypher, and C. T. Ho, “Wildcard dimensions, coding theory and faulttolerant meshes and hypercubes,” IEEE Transaction on Computers, vol. 44, no. 1, pp. 150–155, 1995.

[6] M. Y. Chan, F. Y. L. Chin, and C. K. Poon, “Optimal simulation of full binary trees on faulty hypercubes,” IEEE Transaction on Parallel and Distributed Systems, vol. 6, no. 3, pp. 269–286, 1995.

[7] P. Cull, and S. M. Larson, “The M¨obius cubes,” in Proceedings of the sixth Distrib. Memory Computing Conference, vol. 44, pp. 699–702, 1991.

[8] K. Diks and A. Pele, “Efficient gossiping by packets in networks with random faults,”SIAM Journal on Discrete Mathematics, vol. 9, no. 1, pp. 7–18, 1996.

[9] A. H. Esfahanian and S. L. Hakimi, “Fault-tolerant routing in de Bruijn communication networks,” IEEE Transactions on Computers, vol. C-34, no. 9, pp. 777–788, 1985.

[10] Jianxi Fan, “Diagnosability of th M¨obius Cubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 9, pp. 923–928, 1998.

[11] Jianxi Fan, “Hamiltonian-connectivity and cycle-embedding of the M¨obius cubes,”Information Processing Letters, vol. 82, pp. 113–117, 2002.

[12] Jung-Sheng Fu and Gen-Huey Chen, “Hamiltonicity of the hierarchical cubic network,”Theory of Computing Systems, vol. 35, pp. 59–79, 2002.

[13] Jung-Sheng Fu, “Fault-tolerant cycle embedding in the hypercube,” Parallel Computing, vol. 29, pp. 821-832, 2003.

[14] F. Harary, Graph Theory, Addison-wesley, Massachusetts, 1972.

[15] S. Y. Hsieh and C. H. Chen, “Pancyclicity on M¨obius cubes with maximal edge faults,” Parallel Computing, vol. 30, pp. 407–421, 2004.

[16] D. F. Hsu, “Interconnection Networks and Algorithms,” a special issue of Networks, vol. 23, no. 4, 1993.

[17] W. Huang, Y. Chuang, J. J. M. Tan, L. Hsu, “Fault-free Hamiltonian cycles in faulty M¨obius cubes,” Computaci´on y Systemas, vol. 4, no. 2, pp. 106–114, 2000.

[18] W. T. Huang, W. K. Chen, and C. H. Chen, “Pancyclicity of M¨obius cubes”, in Proceedings of the 9th International Conference on Parallel and Distributed Systems (ICPADS’02), pp. 591–596, 2002.

[19] A. Kanevsky and C. Feng, “On the embedding of cycles in pancake graphs,” Parallel Computing, vol. 21, pp. 923–936, 1995.

[20] H. C. Keh and J. C. Lin, “On fault-tolerant embedding of Hamiltonian cycles, linear arrays and rings in a flexible hypercube,” Parallel Computing, vol. 26, pp. 769–781, 2000.

[21] H. K. Ku and J. P. Hayes, “Optimally edge fault-tolerant trees,” Networks, vol. 27, no. 3, pp. 203–214, 1996.

[22] S. Latifi and N. Bagherzadeh, “Hamiltonicity of the clustered-star graph with embedding applications,” in Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 1996, pp. 734–744.

[23] A. C. Liang, S. Bhattacharya, andW. T. Tsai, “Fault-tolerant multicasting on hypercubes,” Journal of Parallel and Distributed Computing, vol. 23, issue 3, pp. 418–428, 1994.

[24] R. S. Lo and G. H. Chen, “Embedding longest fault-free paths in arrangement graphs with faulty vertices,” Networks, vol. 37, no. 2, pp. 84–93, 2001.

[25] Y. Rouskov, S. Latifi, and P. K. Srimani, “Conditional fault diameter of star graph networks,” Journal of Parallel and Distributed Computing, vol. 33, issue 1, pp. 91–97, 1996.

[26] R. A. Rowley and B. Bose, “Distributed ring embedding in faulty De Bruijn networks,” IEEE Transaction on Computers, vol. 46, no. 2, pp. 187–190, 1997.

[27] H. Sarbazi-Azad, M. Ould-Khaoua, and L. M. Mackenzie, “Algorithmic construction of Hamiltonian in pyramids,” Information Processing Letters, vol. 80, no. 2, pp. 75–79, 2001.

[28] Y. C. Tseng, “Embedding a ring in a hypercube with both faulty links and faulty nodes,” Information Processing Letters, vol. 59, no. 4, pp. 217–222, 1996.

[29] Y. C. Tseng, S. H. Chang, and J. P. Sheu, “Fault-tolerant ring embedding in star graphs with both link and node failures,” IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 12, pp. 1185–1195, 1997.

[30] G. Tel, Topics in distributed algorithms, Cambridge Int’l Series on Parallel Computation, Cambridge University Press, 1991.

[31] M. D.Wagh and J. Mo, “Hamiltonian cycles in trivalent Cayley graphs,” Information Processing Letters, vol. 60, no. 4, pp. 177–181, 1996.

[32] P. J. Yang, S. B. Tien, and C. S. Raghavendra, “Embedding of rings and meshes onto faulty hypercubes using free dimensions,” IEEE Transaction on Computers, vol. C-43, no. 5, pp. 608–613, 1994.