若一個圖G在拿掉k條錯邊之後，在每個點都至少還有三個好的鄰邊的假設之下，任兩個不同的點之間都還存在一條漢米爾頓路徑的話，則此圖G可被稱作是條件式k條邊容錯漢米爾頓連通。在本論文中，我們在有條件的錯誤模式下，討論互連網路上的一種圖族的漢米爾頓連通性，這種圖族稱作侷限類超立方體。我們得到n（n >= 6）維的侷限類超立方體的有條件邊容錯漢米爾頓連通的容錯邊數最多可達2n–7條錯邊。利用我們所得到的定理，我們也將一些知名的網路拓樸結構的漢米爾頓連通的容錯邊數計算出來，例如：交錯超立方體(crossed cubes)、雙扭超立方體(twisted cubes)、局部雙扭超立方體(locally twisted cubes)、廣義雙扭超立方體(generalized twisted cubes) 、莫氏立方體（Möbius cubes）、遞迴環狀圖(recursive circulants)，這些網路拓樸結構的有條件邊容錯漢米爾頓連通都是可以達到2n–7條錯邊。

A graph G is said to be conditional k-edge-fault hamiltonian-connected if after removing k faulty edges from G, under the assumption that each node is incident to at least three fault-free edges, there exists a hamiltonian path between any two distinct nodes in the resulting graph. In this thesis, we consider the conditional edge-fault hamiltonian-connectivity of a wide class of interconnection networks, called restricted hypercube-like networks (RHLs). We proved that an n-dimensional RHL (RHLn) is conditional (2n-7)-edge-fault hamiltonian-connected for n >= 6. We then apply our technical theorems to show that several multiprocessor systems, including n-dimensional crossed cubes, n-dimensional twisted cubes for odd n, n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, n-dimensional Möbius cubes, and recursive circulants G(2^n, 4) for odd n, are all conditional (2n-7)-edge-fault hamiltonian-connected.

[1] N. Ascheuer, Hamiltonian Path Problems in the On-line Optimization of Flexible Manufacturing Systems, PHD thesis, University of Technology, Berlin, Germany, 1995.
[2] Y. A. Ashir and I. A. Stwart, "Fault-Tolerant Embeddings of Hamiltonian Circuits in k-ary n-Cubes," SIAM Journal on Discrete Mathematics, 15(3): 317-328, 2002.
[3] F. T. Boesch and R. Tindell, "Circulants and their connectivities", Journal of Graph Theory, 8(4): 487-499, 1984.
[4] M. Y. Chan and S. J. Lee, "On the Existence of Hamiltonian Circuits in Faulty Hypercubes," SIAM Journal on Discrete Mathematics, 4(4): 511-527, 1991.
[5] J. M. Chang, J. S. Yang, Y. L. Wang, and Y. Cheng, "Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graphs," Networks, 44(4): 302-310, 2004.
[6] F. B. Chedid, "On the generalized twisted cube," Information Processing Letters, 55(1): 49-52, 1995.
[7] X. B. Chen, "Edge-fault-tolerant panconnectivity and edge-pancyclicity of the complete graph," Information Sciences, 235: 341-346, 2013.
[8] C. W. Cheng, C. W. Lee, and S. Y. Hsieh, "Conditional edge-fault Hamiltonicity of Cartesian product graphs," IEEE Transactions on Parallel and Distributed Systems, 24(10): 1951-1960, 2013.
[9] P. Cull and S. M. Larson, "The Möbius cubes," IEEE Transactions on Computers, 44(5): 647-659, 1995.
[10] K. Efe, "The crossed cube architechure for parallel computation," IEEE Transactions on Parallel and Distributed Systems, 3(5): 513-524, 1992.
[11] J. S. Fu, "Fault-tolerant cycle embedding in the hypercube," Parallel Computing, 29(6): 821-832, 2003.
[12] J. S. Fu, "Fault-free Hamiltonian cycles in twisted cubes with conditional link faults," Theoretical Computer Science, 407: 318-329, 2008.
[13] P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. van de Snepscheut, "The twisted cube," in Proceedings of the Conference on Parallel Architectures and Languages Europe, Vol. I: Parallel Architectures, Lecture Notes in Computer Science 258, Springer, New York, pp. 152-159, 1987.
[14] T. Y. Ho, Y. K. Shih, J. M. Tan, and L. H. Hsu, "Conditional fault hamiltonian connectivity of the complete graph," Information Processing Letters, 109: 585-588, 2009.
[15] S. Y. Hsieh, "Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges," Parallel Computing, 32(1): 84-91, 2006.
[16] S. Y. Hsieh, "Some edge-fault-tolerant properties of the folded hypercube," Networks, 51(2): 92-101, 2008.
[17] S. Y. Hsieh and N. W. Chang, "Hamiltonian path embedding and pancyclicity on the Möbius cube with faulty nodes and faulty edges," IEEE Transactions on Computers, 55(7): 854-863, 2006.
[18] S. Y. Hsieh and C. H. Chen, "Pancyclicity in Möbius cubes with maximal edge faults," Parallel Computing, 30(3): 407-421, 2004.
[19] S. Y. Hsieh and Y. R. Cian, "Conditional edge-fault Hamiltonicity of augmented cubes," Information Sciences, 180: 2596-2617, 2010.
[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, 10(3): 223-237, 1999.
[21] S. Y. Hsieh, C. N. Kuo, and H. H. Chou, "A further result on fault-free cycles in faulty folded hypercubes," Information Processing Letters, 110: 41-43, 2009.
[22] S. Y. Hsieh and C. W. Lee, "Conditional Edge-Fault Hamiltonicity of Matching Composition Networks," IEEE Transactions on Parallel and Distributed Systems, 20(4): 581-592, 2009.
[23] S. Y. Hsieh and C. W. Lee, "Pancyclicity of Restricted Hypercube-Like Networks under the Conditional Fault Model," SIAM Journal on Discrete Mathematics, 23(4): 2100-2119, 2010.
[24] S. Y. Hsieh and T. H. Shen, "Edge-bipancyclicity of a hypercube with faulty vertices and edges," Discrete Applied Mathematics, 156(10): 1802-1808, 2008.
[25] S. Y. Hsieh and Y. F. Weng, "Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults," Theory of Computing Systems, 45(2): 407-425, 2009.
[26] S. Y. Hsieh and C. D. Wu, "Optimal fault-tolerant hamiltonicity of star graphs with conditional edge faults," Journal of Supercomputing, 49(3): 354-372, 2009.
[27] S. Y. Hsieh and C. Y. Wu, "Edge-Fault-Tolerant Hamiltonicity of Locally Twisted Cubes under Conditional Edge Faults," Journal of Combinatorial Optimization, 19(1): 16-30, 2010.
[28] H. C. Hsu, L. C. Chiang, J. M. Tan, and L. H. Hsu, "Fault hamiltonicity of augmented cubes," Parallel Computing, 31(1): 131-145, 2005.
[29] H. C. Hsu, Y. L. Hsieh, J. M. Tan, and L. H. Hsu, "Fault Hamiltonicity and Fault Hamiltonian Connectivity of the (n, k)-Star Graphs," Networks, 42(4): 189-201, 2003.
[30] H. C. Hsu, T. K. Li, J. M. Tan, and L. H. Hsu, "Fault Hamiltonicity and Fault Hamiltonian Connectivity of the Arrangement Graphs," IEEE Transactions on Computers, 53(1): 39-53, 2004.
[31] W. T. Huang, Y. C. Chuang, J. M. Tan, and L. H. Hsu, "On the Fault-Tolerant Hamiltonicity of Faulty Crossed Cubes," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E85-A(6): 1359-1370, 2002.
[32] C. W. Huang, H. L. Huang, and S. Y. Hsieh, "Edge-bipancyclicity of star graphs with faulty elements," Theoretical Computer Science, 412: 6938-6947, 2011.
[33] W. T. Huang, J. M. Tan, C. N. Hung, and L. H. Hsu, "Fault-Tolerant Hamiltonicity of Twisted Cubes," Journal of Parallel and Distributed Computing, 62(4): 591-604, 2002.
[34] H. S. Hung, G. H. Chen, and J. S. Fu, "Fault-free Hamiltonian cycles in crossed cubes with conditional link faults," Information Sciences, 177: 5664-5674, 2007.
[35] C. N. Hung, H. C. Hsu, K. Y. Liang, and L. H. Hsu, "Ring embedding in faulty pancake graphs," Information Processing Letters, 86: 271-275, 2003.
[36] S. Y. Kim and J. H. Park, "Paired many-to-many disjoint path covers in recursive circulants (G(2^m, 4))," IEEE Transactions on Computers, 62(12): 2468-2475, 2013.
[37] C. N. Kuo and S. Y. Hsieh, "Pancyclicity and bipancyclicity of conditional faulty folded hypercubes," Information Sciences, 180: 2904-2914, 2010.
[38] C. W. Lee and S. Y. Hsieh, "Pancyclicity of Matching Composition Networks under the Conditional Fault Model," IEEE Transactions on Computers, 61(2): 278-183, 2012.
[39] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, 1992.
[40] J. Li and D. Liu, "k-Pancyclicity of k-ary n-Cube Networks under the Conditional Fault Model," IEEE Transactions on Parallel and Distributed Systems, 23(6): 1115-1120, 2012.
[41] H. S. Lim, H. C. Kim, and J. H. Park, "Hypohamiltonian-Connectedness and Pancyclicity of Hypercube-Like Interconnection Networks with Faulty Elements," in Proceedings of Workshop on Algorithms and Computation(WAAC'05), 2005.
[42] C. K. Lin, T. Y. Ho, J. M. Tan, and L. H. Hsu, "Fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity of the folded Petersen cube networks," International Journal of Computer Mathematics, 86(1): 57-66, 2009.
[43] M. J. Ma, G. Z. Liu, and J. M. Xu, "Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes," Parallel Computing, 33(1): 36-42, 2007.
[44] J. H. Park, "Panconnectivity and edge-pancyclicity of faulty recursive circulant G(2^m, 4)," Theoretical Computer Science, 390: 70-80, 2008.
[45] J. H. Park and K. Y. Chwa, "Recursive circulant : A new topology for multicomputer networks," in Proceedings of Internation Symposium Parallel Architectures, Algorithms and Networks (ISPAN'94), pp. 73-80, 1994.
[46] J. H. Park and K. Y. Chwa, "Recursive circulants and their embeddings among hypercubes," Theoretical Computer Science, 244: 35-62, 2000.
[47] J. H. Park, H. C. Kim, and H. S. Lim, "Fault-Hamiltonicity of hypercube-like interconnection networks," in Proceedings of the 19th IEEE International Parallel and
Distributed Processing Symposium (IPDPS05), Apr. 2005.
[48] J. H. Park, H. C. Kim, and H. S. Lim, "Many-to-many disjoint path covers in the presence of faulty elements," IEEE Transactions on Computers, 58(4): 528-540, 2009.
[49] J. H. Park, H. S. Lim, and H. C. Kim, "Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements," Theoretical Computer Science, 377: 170-180, 2007.
[50] C. H. Tsai, "Linear array and ring embeddings in conditional faulty hypercubes," Theoretical Computer Science, 314: 431-443, 2004.
[51] P. Y. Tsai, J. S. Fu, and G. H. Chen, "Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model," Theoretical Computer Science, 409: 450-460, 2008.
[52] P. Y. Tsai, J. S. Fu, and G. H. Chen, "Embedding Hamiltonian cycles in alternating group graphs under conditional fault model," Information Sciences, 179: 851-857, 2009.
[53] C. H. Tsai, J. M. Tan, and L. H. Hsu, "Hamiltonian Properties of Faulty Recursive Circulant Graphs," Journal of Interconnection Networks, 3(3-4): 273-289, 2002.
[54] 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, 8(12): 1185-1195, 1997.
[55] A. S. Vaidya, P. S. N. Rao, and S. R. Shankar, "A class of hypercube-like networks," in Proceedings of the 5th symposium on Parallel and Distributed Processing, pp. 800-803, 1993.
[56] 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, 62(12): 1747-1762, 2002.
[57] W. W. Wang, M. J. Ma, and J. M. Xu, "Fault-tolerant pancyclicity of augmented cubes," Information Processing Letters, 103: 52-56, 2007.
[58] N. C.Wang, C. P. Yan, and C. P. Chu, "Multicast communication in wormhole-routed symmetric networks with hamiltonian cycle model," Journal of Systems Architecture,
51(3): 165-183, 2005.
[59] D. B. West, "Introduction to Graph Theory," Prentice Hall, NJ, 2 edition, 2001.
[60] X. Yang, D. J. Evans, and G. M. Megson, "The locally twisted cubes," International Journal of Computer Mathematics, 82(4): 401-413, 2005.
[61] X. F. Yang, G. M. Megson, and D. J. Evans, "Pancyclicity of Möbius cubes with faulty nodes," Microprocessors and Microsystems, 30(3): 165-172, 2006.
[62] M. C. Yang, J. M. Tan, and L. H. Hsu, "Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes," Journal of Parallel and Distributed Computing, 67(4): 362-368, 2007.
[63] Computer programs are avaliable at http://algorithm.csie.ncku.edu.tw/HC/