局部雙扭超方體(locally twisted cube)是超立方體(hypercube)的一種變形，其中擁有某些優於超立方體的特性。在這篇論文中，我們研究局部雙扭超方體的邊容錯漢彌爾頓性質(edge-fault-tolerant Hamiltonicity)。我們將證明在每個節點均連接兩條以上好邊的局部雙扭超方體中，當錯邊的個數不超過2n-5，在圖形裡可以找到一條健康(fault-free)的漢彌爾頓圓圈(Hamiltonian cycle)。同時，我們也證明論文中所能容忍的錯邊個數是最佳的。

The locally twisted cube is a variation of hypercube, which possesses some properties superior to the hypercube. In this paper, we investigate the edge-fault-tolerant hamiltoncity of an
n-dimensional locally twisted cube, denoted by LTQn. We show that for any LTQn (n>=3) with at most 2n-5 faulty edges in which each node is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. We also demonstrate that our result is optimal with respect to the number of faulty edges tolerated.

[1] S. G. Akl, Parallel Computation: Models and Methods, Prentice Hall, NJ, 1997.
[2] N. Ascheuer, "Hamiltonian path problems in the on-line optimization of flexible manufacturing systems," Ph.D. Thesis, University of Technology, Berlin, Germany, 1995 (also available from <ftp://ftp.zib.de/pub/zib-publications/reports/TR-96-03.ps>).
[3] Y. A. Ashir and I. A. Stewart, "Fault-tolerant embedding of hamiltonian circuits in k-ary n-cube," SIAM Journal on Discrete Mathematics, vol. 15, no. 3, pp. 317－328, 2002.
[4] M. Y. Chan and S. J. Lee, "On the existence of hamiltonian circuits in faulty hypercubes," SIAM Journal on Discrete Mathematics, vol. 4, no. 4, pp. 511－527, 1991.
[5] C. Chang, T. Sung, and L. Hsu, "Edge congestion and topological properties of crossed cubes," IEEE Transactions Parallel and Distributed Systems, vol. 11, no. 1, pp. 64－80, 2000.
[6] Q. Y. Chang, M. J. Ma, and J. M. Xu, ,"Fault-tolerant pancyclicity of locally twisted cubes," Journal of university of science and Technology of China, vol. 36, no. 6, pp.607－610 and 673, 2006.
[7] P. Cull, and S. M. Larson, "The Mobius cubes," in IEEE Transactions on Computers, vol. 44, no. 5, pp. 647－659, 1995.
[8] K. Day and A. E. Al-Ayyoub, "Fault diameter of k-ary n-cube networks," IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 9, pp. 903－907, 1997.
[9] 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.
[10] K. Efe, "The crossed cube architecture for parallel computation," IEEE Transactions on Parallel and Distributed Sytems, vol. 3, no. 5, pp. 513－524, 1992.
[11] 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, 1958.
[12] J. Fan, "Hamilton-connectivity and cycle-embedding of the Mobius cubes," Information Processing Letters, vol. 82, no. 2, pp. 113－117, 2002.
[13] Jung-Sheng Fu, "Cycle embedding in a faulty hypereube," In Proceeding 9th International Conference Parallel and Distributed Systems, Taiwan, pp. 5－10, 2002.
[14] Jung-Sheng Fu, "Fault-tolerant cycle embedding in the hypercube," Parallel computing, vol. 29, no. 6, pp. 821－832, 2003.
[15] Jung-Sheng Fu, "Conditional fault-tolerant Hamiltonicity of star graphs," Parallel Computing, accepted. A preliminary version of this paper appeared in the Proceedings of 7th Parallel and Distributed Computing, Applications and Technologies (PDCAT'06), pp.11－16, 2006, IEEE Computer Society.
[16] Jung-Sheng Fu, "Conditional fault-tolerant Hamiltonicity of twisted cubes," Proceedings of 7th Parallel and Distributed Computing, Applications and Technologies (PDCAT'06), pp. 5－10, 2006, IEEE Computer Society.
[17] H. S. Hung, G. H. Chen, and J. S. Fu, "Conditional fault-tolerant cycle-embedding of crossed graphs," Proceedings of 7th Parallel and Distributed Computing, Applications and Technologies (PDCAT'06), pp. 90－95, 2006, IEEE Computer Society.
[18] P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. van de Snepscheut, "The twisted cube," Proceedings of the Conference on Parallel Architectures and Languages Europe,
Volume I: Parallel Architectures, Lecture Notes in Computer Science 258, pp. 152－159, 1987.
[19] D. W. Hillis, The Connection Machine, Cambridge, Mass: MIT Press, 1982.
[20] S. Y. Hsieh, C. W. Ho, and G. H. Chen, "Fault-free Hamiltonian cycles in faulty arrangement graphs," IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 3, pp. 223－237, 1999.
[21] S. Y. Hsieh, G. H. Chen, and C. W. Ho, "Longest fault-free paths in star graphs with vertex faults," Theoretical Computer Science, vol. 262, no. 1-2, pp. 215－227, 2001.
[22] S. Y. Hsieh, G. H. Chen, and C. W. Ho, "Longest fault-free paths in star graphs with edge faults," IEEE Transactions on Computers, vol. 50, no. 9, pp. 960－971, 2001.
[23] S. Y. Hsieh, "Embedding longest fault-free paths onto star graphs with more vertex faults," Theortical Computer Science, vol. 337, issues 1－3, pp. 370－378, 2005.
[24] S. Y. Hsieh, "Fault-Tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges," Parallel Computing, vol. 32, issue 1, pp. 84－91, 2006.
[25] W. Huang, J. Tan, C. Hung and L. Hsu, "Fault-tolerant Hamiltonicity of twisted cubes," Journal Parallel and Distributed Computing, vol. 62, no. 4, pp. 591－604, 2002.
[26] W. Huang, Y. Chuang, J. Tan and L. Hsu, "On the fault-tolerant Hamiltonicity of faulty crossed cubes," IEICE Transactions Fundamentals, E85-A, no. 6, pp.1359－1370, 2002.
[27] W. Huang, W. Chen and C. Chen, "On the fault-tolerant pancyclicity of crossed cubes," In Proceeding 9th International Conference Parallel and Distributed Systems, Taiwan, pp. 591－596, 2002.
[28] W. Huang, Y. Chuang, J. Tan and L. Hsu, "Fault-free Hamiltonian cycle in faulty Mobius cubes," Journal Computing and Systems, vol. 4, pp. 106－114, 2000.
[29] H. S. Hung, "Fault-tolerant computation on crossed cubes with conditional faults," Ph.D. thesis, Department of Computer Science and Information Engineering, National
Taiwan University, Taipei, Taiwan, 2006.
[30] S. Latifi, S. Zheng and N. Bagherzadeh, "Optimal ring embedding in hypercubes with faulty links," In Digest 22nd Symposium Fault-Tolerant Computing, pp. 178－184, 1992.
[31] F. T. Leighton, Introduction to parallel algorithms and architecture: arrays trees hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
[32] A. C. Liang, S. Bhattacharya, and W. T. Tsai, "Fault-tolerant multicasting on hypercubes," Journal of Parallel and Distributed Computing, vol. 23, pp. 418－428, 1994.
[33] M.J. Ma, J.M. Xu, "Panconnectivity of locally twisted cubes," Applied Mathematics Letters, vol. 19, no. 7, pp. 673－677, 2006.
[34] B. Parhami, Introduction to Parallel Processing: Algorithms and Architectures, Plenum Press, New York, 1999.
[35] J. H. Park, H. C. Kim, and H. S. Lim, "Fault- Hamiltonicity of hypercube-like interconnection networks," Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium, 2005 (IPDPS'05), vol. 1, pp. 60.1, 2005.
[36] N. Singhvi and K. Ghose, "The Mcube: a symmetrical cube based network with twisted links," Proceedings of the 9th International Symposium of Parallel Processing, Honolulu, pp. 11－16, 1995.
[37] C. H. Tsai, "Linear array and ring embeddings in conditional faulty hypercubes," Theoretical Computer Science, vol. 314, pp. 431－443, 2004.
[38] Y. C. Tseng, S. H. Chang, and J. P. Sheu, "Fault-tolerant ring embedding in a star graph with both link and node failures," IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 12, pp. 1185－1195, 1997.
[39] Y. C. Tseng, "Resilient and flexible ring embedding in an injured hypercube," Journal Information Science and Engineering, vol. 12, no. 4, pp. 567－583, 1996.
[40] Y. C. Tseng, "An efficient scheme for embedding a ring into an injured hypercube with both faulty links and faulty nodes," In Proceeding 3rd International Conference High Performance Computing, pp. 165－169, 1996.
[41] N. C. Wang, C. P. Chu, and T. S. Chen, "A dual-Hamiltonian-path-based multicasting strategy for wormhole-routed star graph interconnection networks," Journal of Parallel and Distributed Computing, vol. 62, issue 12, pp. 1747－1762, 2002.
[42] N. C. Wang, C. P. Yen, and C. P. Chu, "Multicast communication in wormhole-routed symmetric networks with Hamiltonian cycle model," Journal of Systems Architecture,
vol. 51, issue 3, pp. 165－183, 2005.
[43] C. Y. Wu, "The supplements of two disjoint paths visiting all nodes in locally twisted cubes," http://algorithm.csie.ncku.edu.tw/~hooh.
[44] J. Wu, "Safety levels-an efficient mechanism for achieving reliable broadcasting in hypercubes," IEEE Transactions on Computers, vol. 44, no. 5, pp. 702－706, 1995.
[45] 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, vol. 43, no. 5, pp. 608－613, 1994.
[46] X. F. Yang, D. J. Evans, and G. M. Megson, "Locally twisted cubes are 4-pancyclic," Applied Mathematics Letters , vol. 17, no. 8, pp. 919－925, 2004.
[47] X. F. Yang, D. J. Evans, and G. M. Megson, "The locally twisted cubes," International Journal of Computer Mathematics, vol. 82, no. 4, pp. 401－413, 2005.