本篇論文中 , 我們定義在 n 維的超立方體中 , f_v 代表毀損點的總數 , f_e 代表毀損邊的總數 。
我們證明結果在 n維的超立方體中 , 嵌入一個長度至少是 2^n-2f_v 的fault-free環 ,可以容錯 f_e <= n-2 和 f_v+f_e <= 2n-4 。
我們的論文不只是改善 Sengupta(1998) 到目前為止最好的結果 ,容錯 f_e>0 或 f_v <= n-2 和 f_v+f_<= n-1 。
而且還是延伸 Fu (2003)的論文 , 其中只討論毀損點 。

　　Let f_v (respectively, f_e) denote the number of faulty vertices(respectively, edges) in an n-dimensional hypercube 。
In this paper ,we show that a fault-free cycle of length at least 2^n-2f_v can be embedded in an n-dimensional hypercube with f_e <= n-2 and f_v+f_e <= 2n-4 。
Our result not only improve the previously best known result of Sengupta (1998) where f_e>0 or f_vleqslant n-2 and f_v+f_e <= n-1 were assumed , but also extends the result of Fu (2003) where only the faulty vertices are considered 。

[1] S.G.Akl, Parallel Computation:Models and Methods.
Prentice Hall,(1997)
[2] B.Alspach , J.C.Bermond , and D.Sotteau , "Decomposition into Cycles I. Hamiltonian Decomposition" ,
Theory of Computing Systems , Technical Report 87-
12 , Simon Fraser University (1987) .
[3] J.Bruck, R. Cypher, and D. Soroker , "Embedding cube-connected-cycles graphs into faulty hyper-
cubes", IEEE Transactions on Computers, vol.43, no.10, pp.1210{1220,(1994).
[4] M. Y. Chan and S. J. Lee , "Distributed Fault-Tolerant Embeddings of Rings in Hypercubes" , Jour-
nal of Parallel and Distributed Computing , 11 , pp.63-71 (1991) .
[5] M. Y. Chan and S. J. Lee , "Fault-tolerant Embeddings of complete binary trees in Hypercubes" , IEEE
Transactions on Parallel and Distributed Systems , vol.4 ,no.3, pp. 540-547 (1993).
[6] M. Y. Chan and K. G. Shin , "Processor allocation in an n-cube multiprocessor using gray codes" , IEEE
Transactions on Computers , vol.C-36, pp. 1396-1407 (1987) .23
[7] Jung-Sheng Fu , "Fault-tolerant cycle embedding in
the Hypercube" , Parallel Computing , vol.29 , pp. 821-832 (2003) .
[8] Jung-Sheng Fu and Gen-Huey Chen , "Hamiltonicity of the Hierarchical Cubic Network" , Theory of Computing Systems , vol.35 , pp. 59-79 (2002) .
[9] S.Y.Hsieh ,and G.H. Chen and C.W. Ho, " Embed longest rings onto star graphs with vertex faults" , in
Proceedings of the International Conference on Parallel Processing , pp. 140-147 (1998) .
[10] Chien-Hung Huang , Ju-Yuan Hsiao and R.C.T. Lee, "An optimal embedding of cycles into incomplete
hypercubes", Information Processing Letters , vol.72 ,pp. 213-218 (1999) .
[11] S. Lati , S. Q. Zheng , N. Bagherzadeh , " Optimal ring embedding in Hypercubes with faulty links " ,
Processings of the IEEE Symposium on Fault-Tolerant Computing , pp. 178-184 (1992) .
[12] F. T. Leighton , " Introduction to Parallel Algorithms and Architecture:Array Trees Hypercubes" Morgan
Kaufmann, San Mateo, CA, (1992).
[13] R.A.Rowley and B.Bose , " Fault-tolerant ring embedding in deBruijn networks", IEEE Transactions on
Computers, vol.42, no.12, pp.1480-1486,(1993)24
[14] A.Sen, A.sengupta, and S.Bandyopadhyay, "On some topological properties of hypercube,incomplete hyper-
cube and supercube" in Proceedings of the International Parallel Processing Symposium Newport Beach,
April,pp.636-642,(1993).
[15] Abhijit Sengupta , "On ring embedding in hypercubes with faulty nodes and links" , Information Processing
Letters , 68 , pp.207-214 (1998) .
[16] G.Tel, Topics in distributed algorithms. Cambridge Int'l Series on Parallel Computation, Cambridge Universitry Press,(1991).
[17] Chang-Hsiung Tsai, Jimmy J.M.Tam , Tyne Liang, and Lih-Hsing Hsu, "Fault-tolerant hamiltonian laceability of hypercubes", Information Processing Letters, vol.83, no.6, pp.301-306,(2002).
[18] Yu-Chee Tseng , "Embedding a ring in a hypercube with both faulty links and faulty nodes" , Information Processing Letters , 59 , pp. 217-222 (1996) .
[19] Yu-Chee 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)25
[20] Yu-Chee Tseng , T.H. Lai , "On the embedding of aclass of regular graphs in a faulty hypercube ", Journal
of Parellel Distributed Computing , vol.37, pp. 200-206,(1996)
[21] D.B.West, Introduction to Graph Theory. Prentice-Hall, Upper Saddle River, NJ 07458,(2001)
[22] P. J. Yang , C. S. Raghavendra , "Embedding and recon guration of binary trees in faulty hypercubes" ,
IEEE Transactions on Parallel Distributed Systems , vol.7, no.3 , pp.237-245 (1996) .
[23] P. J. Yang , S. B. Tien and C. S. Raghavendra , "Embedding of rings and meshes onto faulty Hypercubes
using free dimensions" , IEEE Transactions on Computers , 43(5) , pp. 608-613 (1994) .