在科技日新月異的現在，建構一個平行分散式系統往往都需要成千上萬個處理器，尤其是在VLSI的技術中，所需要的個數更多。設計一個大型的平行分散式系統中，一個很重要的步驟就是去討論其互連網路的拓樸結構特性。對於一個互連網路而言，從一個網路拓樸結構模擬成另外一個網路拓樸結構的方式，被稱之為網路嵌入問題。而迴圈是一個很基本的網路拓樸結構，很適合發展出一套有效率且低通訊成本的演算法。因為迴圈有廣大的應用，所以我們對於迴圈嵌入網路的問題感到興趣。在過去的一些研究成果中，有部分是在討論是否可以找到最大長度的迴圈，也就是圖形理論所討論的漢米爾頓迴圈問題；有部分是在討論是否可以找到各種長度的迴圈，也就是圖形理論所討論的泛迴圈問題。
因為在網路使用的過程中，可能會有邊連線上或處理器上的錯誤發生，因此解決在錯誤的網路系統上的問題是很重要的。對於一個互連網路拓樸結構而言，其容錯的能力是很重要的。也就是說當一個網路系統發生處理器或是連線發生錯誤時，這個網路系統是否還是能夠維持運作。在過去的研究當中，有兩種不同的錯誤模式。一種是標準的錯誤模式，這是一種沒有任何限制的錯誤模式；另一種是有條件的錯誤模式，這一種錯誤模式是假設在錯誤發生的情形下，每一個處理器都還保有兩條邊是好的。而解決有條件的錯誤模式下的問題，會比解決標準的模式下來得困難。
在本論文中，我們在有條件的錯誤模式下，討論兩種圖族的迴圈容錯嵌入問題，這兩種圖族分別是侷限類超立方體，以及配對構成網路。我們得到n維的侷限超立方體的有條件邊容錯泛迴圈的容錯邊數最多可達2n–5條錯邊，而且這個結果是最佳的。利用我們所得到的定理，我們也將一些知名的網路拓樸結構的容錯邊數計算出來，例如：交錯超立方體(crossed cubes)、雙扭超立方體(twisted cubes)、局部雙扭超立方體(locally twisted cubes)、廣義雙扭超立方體(generalized twisted cubes)、遞迴環狀圖(recursive circulants)，這些網路拓樸結構的有條件邊容錯泛迴圈都是可以達到2n–5條錯邊。
更進一步，我們討論在配對構成網路中，其有條件邊容錯漢米爾頓迴圈的性質。我們討論得到在一些共同的條件下，計算出該配對構成網路的容錯能力。接著把這個定理應用到知名的網路拓樸結構中，計算其有條件邊容錯漢米爾頓迴圈的容錯邊數，例如：hyper-Petersen networks。

Advances in technology, especially the advent of VLSI circuit technology, have made it possible to build a large parallel and distributed system involving thousands or even tens of thousands of processors. One crucial step on designing a large-scale parallel and distributed system is to determine the topology of the interconnection network. For interconnection networks, the problem of simulating one network by another is modelled as a network embedding problem. Cycles, which is one of the most fundamental interconnection networks for parallel and distributed computation, is suitable to develop simple and e±cient algorithms with low communication costs. The wide applications of cycles motivate us to investigate cycle embedding in networks. Some of previous researched on cycle embedding focus on finding longest cycles, that is, the Hamiltonian problem. Some others focused on ¯nding cycles of all possible lengths, that is, the pancycle problem.
Since edge (link) faults may occur when a network is activated, it is important to solve problems in faulty networks. Fault tolerance ability is an important consideration for interconnection network topology. That is, the network is still functional when some node faults and/or link faults occur. Among the results reported, there are two assumptions about faulty edges. The first is the standard fault-assumption, under which there is no restriction on the distribution of faulty edges. The second is the conditional fault-assumption, under which each node is incident to at least two fault-free edges. It is more di±cult to solve problems under the conditional fault model than the standard fault model.
In this dissertation, we investigate fault-free cycle embedding problems with edge faults on two wide classes of interconnection networks, called restricted hypercube-like networks and matching composition networks under the conditional fault model. We showed that an n-dimensional restricted hypercube-like networks (RHL_n) is (2n-5)-edge-fault pancyclicity. This result is optimal with respect to the number of edge faults tolerant. By applying our technical theorems, we have successfully demonstrated the conditional edge-fault pancyclicity of several multiprocessor systems, n-dimensional crossed cubes, n-dimensional twisted cubes for odd n, n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, and recursive circulants G(2^n; 4) for odd n, are all conditional (2n - 5)-edge-fault pancyclic.
Moreover, we sketch common properties of Matching Composition Networks (MCNs) such that the conditional edge-fault Hamiltonicity of MCNs can be determined from the obtained properties. We then apply our technical theorems to determine conditional edge-fault Hamiltonicities of multiprocessor system, such as n-dimensional hyper-Petersen networks.

[1] S. Abraham and K. Padmanabhan, "The twisted cube topology for multiprocessors: a study in network asymmetry," Journal of Parallel and Distributed Computing, 13: 104-110, 1991.
[2] A. E. AI-Ayyoub and K. Day, "Comparative study of product networks," Journal of Parallel and Distributed Computing, 62(1):1-18, 2002.
[3] S. B. Akers, D. Horel, and B. Krishnamurthy, "The star graph: an attractive alternative to the n-cube," in Proceeding of the international Conference on Parallel Processing, pages 393-400, 1987.
[4] S. B. Akers and B. Krishnamurthy, "A group-theoretic model for symmetric interconnection networks," IEEE Transactions on Computers, 38(4): 555-566,1989.
[5] S. G. Akl, Parallel Computation: Models and Methods, Prentice Hall, NJ, 1997.
[6] B. Alspach and D. Hare, "Edge-pancyclic block-intersection graphs," Discrete Mathematics, 97(1-3): 17-24, 1991.
[7] N. Ascheuer, Hamiltonian path problems in the on-line optimization of flexible manufacturing systems, PhD thesis, University of Technology, Berlin, Germany, 1995.
[8] 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.
[9] N. Bagherzadeh, N. Nassif, and S. Latifi, "A routing and brocasting scheme on faulty star graphs," IEEE Transactions on Computers, 42(11): 1398-1403, 1993.
[10] F. T. Boesch and R. Tindell, "Circulants and their connectivities," Journal of Graph Theory, 8:129-138, 1984.
[11] J. A. Bondy, "Pancyclic graphs," Journal of Combinatorial Theory, Series B, 11: 80-84, 1971.
[12] 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.
[13] M. Y. Chan and S. J. Lee, "Distributed fault-tolerant embedding of rings in hypercubes," Journal of Parallel Distributed Computing, 11: 80-84, 1991.
[14] C. P. Chang, J. N. Wang, L. H. Hsu, "Topological properties of twisted cubes," Information Sciences, 113: 147-167, 1999.
[15] C. P. Chang, T. Y. Sung, and L. H. Hsu, "Edge congestion and topological properties of crossed cube," IEEE Transactions on Parallel and Distributed Systems, 11(1): 64-80, 2000.
[16] J. M. Chang and J. S. Yang, "Fault-tolerant cycle-embedding in alternating group graphs," Applied Mathematics and Computation, 197: 760-767, 2008.
[17] 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.
[18] Q. Y. Chang, M. J. Ma, and J. M. Xu, "Fault-tolerant pancyclicity of locally twisted cubes (in Chinese)," Journal of University of Science and Technology of China, 36(6): 607-610, 2006.
[19] Q. Y. Chang, M. J. Ma, and J. M. Xu, "Fault-tolerant pancyclicity of twisted cubes (in Chinese)," Operation Research and Management Science, 16(1): 52-57, 2007.
[20] F. B. Chedid, "On the generalized twisted cube," Information Processing Letters, 55(1):49-52, 1995.
[21] F. B. Chedid and R. B. Chedid, "A new variation on hypercubes with smaller diameter," Information Processing Letters, 46(6):275-280, 1993.
[22] Y. C. Chen, C. H. Tsai, L. H. Hsu, and J. J. M. Tan, "On some super fault-tolerant Hamiltonian graphs," Applied Mathematics and Computation, 148: 729-741, 2004.
[23] S. A. Choudum and V. Sunitha, "Augmented cubes," Networks, 40(2): 71-84, 2002.
[24] P. Corbett, "Rotator graphs: an efficient topology for point-to-point multiprocessor networks," IEEE Transactions on Parallel and Distributed Systems, 3(5): 622-626, 1992.
[25] P. Cull and S. M. Larson, "The Mobius cubes," IEEE Transactions on Computers, 44(5):647-659, 1995.
[26] S. K. Das and A. K. Banerjee, "Hyper Petersen network: Yet another hypercube-like topology," in Proceedings of the 4th Symposium on the Frontiers of Massively Parallel Computation (Froniters'92), pages 270-277, McLean, Virginia, USA, IEEE Computer Society, 1992.
[27] S. K. Das, S. Ä Ohring, and A. K. Banerjee, "Embeddings into hyper Petersen networks: Yet another hypercube-like interconnection topology," VLSI Design, 2(4):335-351, 1995.
[28] K. Day and A. E. Al-Ayyoub, "Fault diameter of k-ary n-cube networks," IEEE Transactions on Parallel and Distributed Systems, 8(9): 903-907, 1997.
[29] K. Day and A. Tripathi, "Arrangement graphs: a class of generalized star graphs," Information Processing Letters, 42(5): 235-241, 1992.
[30] K. Day and A. Tripathi, "Embedding of cycles in arrangement graphs," IEEE Transactions on Computers, 42(8): 1002-1006, 1993.
[31] K. Diks and A. Pele, "Efficient gossiping by packets in networks with random faults," SIAM Journal on Discrete Mathematics, 9(1): 7-18, 1996.
[32] Z. Z. Du, J. Jing, M. J. Ma, and J. M. Xu, "Cycle embedding in hypercubes with faulty vertices and edges," Journal of University of Science and Technology of China, 2007.
[33] K. Efe, "A variation on the hypercube with lower diameter," IEEE Transactions on Computers, 40(11): 1312-1316, 1991.
[34] K. Efe, "The crossed cube architecture for parallel computation," IEEE Transactions on Parallel and Distributed Systems, 3(5):513-524, 1992.
[35] K. Efe, P. K. Blackwell, W. Slough, and T. Shiau, "Topological properties of the crossed cube architechure," Parallel Computing, 20: 1763-1775, 1994.
[36] A. El-amawy and S. Latifi, "Properties and performance of folded hypercubes," IEEE Transactions on Parallel and Distributed Systems, 2(1): 31-42, 1991.
[37] A. H. Esfahanian and S. L. Hakimi, "Fault-tolerant routing in de bruijn communication networks," IEEE Transactions on Computers, C-34(9): 777-788, 1985.
[38] A. H. Esfahanian, L. M. Ni, and B. E. Sagan, "The twisted N-cube with application to multiprocessing," IEEE Transactions on Computers, 40(1): 88-93, 1991.
[39] J. Fan, "Hamiltonian-connected and cycle-embedding of the Mobius cubes," Information Processing Letters, 82: 113-117, 2002.
[40] J. Fan and L. He, "BC interconnection networks and their properties," Chinese Journal of Computers, vol. 26, no. 1, pp. 84-90, 2003.
[41] J. Fan, X. Lin and X. Jia, "Node-pancyclicity and edge-pancyclicity of crossed cubes," Information Processing Letters, 93(3): 133-138, 2005.
[42] J. S. Fu, "Fault-tolerant cycle embedding in the hypercube," Parallel Computing, 29: 821-832, 2003.
[43] J. S. Fu, "Fault-tolerant cycle embedding in hieraechical cubic networks," Networks, 43(1): 28-38, 2004.
[44] J. S. Fu, "Fault-free Hamiltonian cycles in twisted cubes with conditional link faults," Theoretical Computer Science, 407(1-3): 318-329, 2008.
[45] J. S. Fu, "Conditional fault-tolerant hamtiltonicity of star graph," Parallel Computing, 33: 488-496, 2007.
[46] J. S. Fu, "Conditional fault Hamiltonicity of the complete graph," Information Processing Letters, 107(3{4): 110-113, 2008.
[47] A. Germa, M. C. Heydemann, and D. Sotteau, "Cycles in the cube-connected cycles graph," Discrete Applied Mathematics, 83(1): 135-155, 1998.
[48] K. Ghose and K. R. Desai, "Hierarchical cubic networks," IEEE Transactions on Parallel and Distributed Systems, 6(4): 427-435, 1995.
[49] F. Harary, "Conditional connectivity," Networks, 13: 347-357, 1983.
[50] 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, Volume I: Parallel Architectures, pages 152-159, 1987.
[51] W. D. Hillis, The Connection Machine, MIT Press, Cambridge, MA, 1985.
[52] M. R. Hoseinyfarahabady and H. Sarbazi-azad, "The grid-pyramid: a generalized pyramid network," Journal of Supercomputing, 37: 23-45, 2006.
[53] S. Y. Hsieh, "Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edge," Parallel Computing, 32(1): 84-91, 2006.
[54] S. Y. Hsieh, "A note on cycle embedding in folded hypercubes with faulty elements," Information Processing Letters, 108(2): 81, 2008.
[55] S. Y. Hsieh and N. W. Chang, "Hamiltonian path embedding and pancyclicity on the Mobius cube with faulty nodes and faulty edges," IEEE Transactions on Computer, 55(7):854-863, 2006.
[56] S. Y. Hsieh and C. H. Chen, "Pancyclicity in Mobius cubes with maximal edge faults," Parallel Computing, 30(3): 407-421, 2004.
[57] S. Y. Hsieh, G. H. Chen, and C. W. Ho, "Fault-free hamiltonian cycles in faulty arrangement graphs," IEEE Transactions on Parallel and Distributed Systems, 10(3): 223-237, 1999.
[58] S. Y. Hsieh, G. H. Chen, and C. W. Ho, "Hamiltonian-laceability of star graphs," Networks, 36(4): 225-232, 2000.
[59] S. Y. Hsieh, G. H. Chen, and C. W. Ho, "Longest fault-free paths in star graphs with edge faults," IEEE Transactions on Computers, 50(9): 960-971, 2001.
[60] S. Y. Hsieh, G. H. Chen, and C. W. Ho, "Longest fault-free paths in star graphs with vertex faults," Theoretical Compurt Science, 262(1-2): 215-227, 2001.
[61] S. Y. Hsieh and C. W. Lee, "Conditional edge-fault hamiltonicity of matching composition networks," IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 4, pp. 581-592, 2009.
[62] S. Y. Hsieh, T. J. Lin, and H. L. Huang, "Panconnectivity and edge-pancyclicity of 3-ary N-cubes," Journal of Supercomputing 42: 225-233, 2007.
[63] 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.
[64] S. Y. Hsieh and J. Y. Shiu, "Cycle embedding of augmented cubes," Applied Mathematics and Computation, 191: 314-319, 2007.
[65] 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.
[66] W. J. Hsu, "Fibonacci cubes - a new interconnection topology," IEEE Transactions on Parallel and Distributed Systems, 4(1): 3-12, 1993.
[67] H. C. Hsu, L. C. Chiang, J. J. M. Tan, and L. H. Hsu, "Fault Hamiltonicity of augmented cubes," Parallel Computing, 31(1): 131-145, 2005.
[68] H. C. Hsu, Y. L. Hsieh, J. 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.
[69] H. C. Hsu, T. K. Li, J. J. M. Tan, and L. H. Hsu, "Fault Hamiltonicity and fault Hamiltonian connectivity of arrangement graphs," IEEE Transactions on Computers, 53(1): 39-52, 2004.
[70] W. T. Huang, Y. C. Chuang, L. H. Hsu, and J. J. M. Tan, "On the fault-tolerant Hamiltonicity of crossed cubes," IEICE Transactions on Fundamentals, E85-A(6): 1359-1371, 2002.
[71] W. T. Huang, J. M. Tan, C. N. Hung, and L. H. Hsu, "Fault-tolerant Hamiltonianicity of twisted cubes," Journal of Parallel and Distributed Computing, 62: 591-604, 2002.
[72] H. S. Hung, G. H. Chen, and J. S. Fu, "Fault-free Hamiltonian cycles in crossed cubes with conditional link faults," Information Sciences, vol. 177, issue 24, pp. 5664-5674, 2007.
[73] H. S. Hung, J. S. Fu, and G. H. Chen, "Pancycle problem of crossed cube with conditional faults," in Proceedings of the International Computer Symposium (ICS'06), pages 153-158, Taipei, Taiwan, 2006.
[74] C. N. Hung, H. C. Hsu, K. Y. Liang, and L. H. Hsu, "Ring embedding in faulty oancake graphs," Information Processing Letters, 86: 271-275, 2003.
[75] K. Hwang and J. Ghosh, "Hypernet: a communication-efficient architechure for constructing massively parallel computers," IEEE Transactions on Computers, 36(12): 1450-1466, 1987.
[76] S. C. Hwang and G. H. Chen, "Cycles in butterfly graphs," Networks, 35(2): 161-171, 2000.
[77] J. S. Jwo, S. Lakshmivarahan, and S. K. Dhall, "Embedding of cycles and grids in star graphs," Journal of Circuits, Systems, and Computers, 1(1): 43-74, 1991.
[78] J. S. Jwo, S. Lakshmivarahan, and S. K. Dhall, "A new class of interconnection networks based on the alternating group," Networks, 23: 315-326, 1993.
[79] A. Kanevsky and C. Feng, "On the embedding of cycles in pancake graphs," Parallel Computing, 21: 923-936, 1995.
[80] Y. Kikuchi and T. Araki, "Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs," Information Processing Letters, 100(2): 52-59, 2006.
[81] M. S. Krishnamoorthy and B. Krishnamurthy, "Fault diameter of interconnection networks," Computers and Mathematics with Applications, 13(5-6): 577-582, 1987.
[82] S. C. Ku, B. F. Wang, and T. K. Hung, "Constructing edge-disjoint spanning trees in product networks," IEEE Transactions on Parallel and Distributed Systems, 14(3):213-221, 2003.
[83] P. Kulasinghe and S. Betayeb, "Embedding binary trees into crossed cubes," IEEE Transactions on Computers, 44(7): 923-929, 1995.
[84] P. Kulasinghe, "Connectivity of the crossed cube," Information Processing Letters, 61: 221-226, 1997.
[85] P. L. Lai, J. J. M. Tan, C. H. Tsai, and L. H. Hsu, "Diagnosability of the matching composition network under the comparison diagnosis model," IEEE Transactions on Computers, vol. 53, no. 8, pp. 1064-1069, 2004.
[86] S. M. Larson and P. Cull, "The Mobius cubes," IEEE Transactions on Computers, 44(5): 647-659, 1995.
[87] S. Latifi, "Combinatorial analysis of the fault-diameter of the n-cube," IEEE Transactions on Computers, 42(1): 27-33, 1993.
[88] S. Latifi, "On the fault-diameter of the star graph," Information Processing Letters, 46: 143-150, 1993.
[89] F. T. Leighton, Introduction to parallel algorithms and architecture: arrays. trees. hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
[90] Y. R. Leu and S. Y. Kuo, "Distributed fault-tolerant ring embedding and reconfiguration in hypercubes," IEEE Transactions on Computers, 48(1): 81-88, 1999.
[91] T. K. Li, "Cycle embedding in star graphs with edge faults," Applied Mathematics and Computation, 167(2): 891-900, 2005.
[92] T. K. Li, M. C. Yang, J. M. Tan, and L. H. Hsu, "On embedding cycle in faulty twisted cubes," Information Sciences, 176: 676-690, 2006.
[93] S. C. Liaw, G. J. Chang, F. Cao, and D. F. Hsu, "Fault-tolerant routing in circulant networks and cycle pre¯x networks," Annals of Combinatorics, 2: 165-172, 1998.
[94] 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), Seoul, Korea, Aug. 2005.
[95] H. S. Lim, J. H. Park, and K. Y. Chwa, "Embedding trees into recursive circulants," Discrete Applied Mathematics, 69: 83-99, 1996.
[96] X. Lin and P. K. McKinley, "Deadlock-free multicast wormhole routing in 2-D mesh multicomputers," IEEE Transactions on Parallel and Distributed Systems, 5: 793-804, 1994.
[97] C. K. Lin, T. Y. Ho, J. 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.
[98] 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.
[99] M. J. Ma, J. M. Xu, and Z. Z. Du, "Edge-fault-tolerant Hamiltonicity of folded hypercubes," Journal of University of Science and Technology of China, 36(3): 244-248, 2006.
[100] J. H. Park, "Unpaired many-to-many disjoint path covers in hypercube-like interconnection networks," Journal of KISS, 33(10):789-796, 2006.
[101] J. H. Park, "Panconnectivity and edge-pancyclicity of faulty recursive circulant G(2m; 4)," Theoretical Computer Science, 390(1):70-80, 2008.
[102] 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), pages 73-80. IEEE press, New York, 1994.
[103] J. H. Park and K. Y. Chwa, "Recursive circulants and their embeddings among hypercubes," Theoretical Computer Science, 244:35-62, 2000.
[104] 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 (IPDPS'05), Denver, CA, USA, Apr. 2005. IEEE Computer Society.
[105] J. H. Park, H. C. Kim, and H. S. Lim, "Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements," IEEE Transactions on Parallel and Distributed Systems, 17(3): 227-240, 2006.
[106] J. H. Park, H. S. Lim, and H. C. Kim, "Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements," Theortical Computer Science, 377:170-180, 2007.
[107] F. Preparate and J. Vuillemin, "The cube-connected cycles: a versatile network for parallel computation," Communications of the ACM, 24(5): 300-309, 1981.
[108] Y. Rouskov, S. Latifi, and P. K. Srimani, "Conditional fault diameter of star graph networks," Journal of Parallel and Distributed Computing, 33(1): 91-97, 1996.
[109] Y. Rouskov and P. K. Srimani, "Fault diameter of star graph," Information Processing Letters, 48: 243-251, 1993.
[110] R. A. Rowley and B. Bose, "Fault-tolerant ring embedding in de bruijn networks," IEEE Transactions on Computers, 42(12): 1480-1486, 1993.
[111] R. A. Rowley and B. Bose, "Distributed ring embedding in faulty de bruijn networks," IEEE Transactions on Computers, 46(2): 187-190, 1997.
[112] Y. Saad and M. H. Schultz, "Topological properties of hypercubes," IEEE Transactions on Computers, 37(7): 867-872, 1988.
[113] M. R. Samatham and D. K. Pradhan, "The de bruijn multiprocessor network: a versatile parallel processing and sorting network for VLS," IEEE Transactions on Computers, 38: 567-581, 1989.
[114] A. Sengupta, "On ring embedding in hypercubes with faulty nodes and links," Information Processing Letters, 68(4): 207-214, 1998.
[115] H. S. Stone, "Parallel processing with the perfect shu²e," IEEE Transactions on Computers, 20(2): 153-161, 1971.
[116] C. H. Tsai, "Linear array and ring embeddings in conditional faulty hypercubes," Theortical Computer Science, 314:431-443, 2004.
[117] 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(3): 450-460, 2008.
[118] P. Y. Tsai, J. S. Fu, and G. H. Chen, "Embedding Hamiltonian cycles in alternating group graphs under conditional fault model," Information Sciences, 179(6): 851-857, 2009.
[119] C. H. Tsai and Y. C. Lai, "Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes," Information Sciences, 177(24): 5590-5597, 2007.
[120] 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.
[121] Y. C. Tseng, M. H. Yang, and T. Y. Juang, "Achieving fault-tolerant multicast in injured wormhole-routed tori and meshed based on Euler path construction," IEEE Transactions on Computers, 48: 1282-1296, 1999.
[122] A. S. Vaidya, P. S. N. Rao, and S. R. Shankar, "A class of hypercube-like networks," in Proceedings of the 5th IEEE Symposium on Parallel and Distributed Proceeding (SPDP'93), pages 800-803, Dec 1993.
[123] G. D. Vecchia and C. Sanges, "A recursively scalable network VLSI implementation," Future Generation Computer Systems, 4(3): 235-243, 1988.
[124] D. J. Wang, "Embedding Hamiltonian cycles into folded hypercubes with faulty links," Journal of Parallel and DistributedComputing, 61: 545-564, 2001.
[125] 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.
[126] W. W. Wang, M. J. Ma, and J. M. Xu, "Fault-tolerant pancyclicity of augmented cubes," Information Processing Letters, 103(2):52-56, 2007.
[127] 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.
[128] D. B. West, Introduction to Graph Theory, Prentice Hall, NJ, 2 edition, 2001.
[129] S. A. Wong, "Hamiltonian cycles and paths in butter°y graphs," Networks, 26:145-150, 1995.
[130] J. Wu, "Safety levels - an e±cient mechanism for achieving reliable broadcasting in hypercubes," IEEE Transactions on Computers, 44(5): 702-706, 1995.
[131] J. M. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, Dordrecht/Boston/London, 2001.
[132] J. M. Xu, Z. Z. Du, and M. Xu, "Edge-fault-tolerant edge-bipancyclicity of hypercubes," Information Processing Letters, 96(4): 146-150, 2005.
[133] J. M. Xu and M. J. Ma, "Cycles in folded hypercubes," Applied Mathematics Letters, 19(2): 140-145, 2006.
[134] M. C. Yang, T. K. Li, J. J. M. Tan, and L. H. Hsu, "Fault-tolerant cycle-embedding of crossed cubes," Information Processing Letters, 88: 149-154, 2003.
[135] X. F. Yang, D. J. Evans, and G. M. Megson, "The locally twisted cubes," International Journal of Computer Mathematics, 82(4):401-413, 2005.
[136] X. F. Yang, G. M. Megson, and D. J. Evans, "Locally twisted cubes are 4-pancyclic," Applied Mathematic Letters, 17: 919-925, 2004.
[137] X. F. Yang, G. M. Megson, and D. J. Evans, "Pancyclicity of MÄobius cubes with faulty nodes," Microprocessors and Microsystems, 30(3):165-172, 2006.
[138] P. J. Yang, S. B. Tien, and C. S. Raghavendra, "Embedding of rings amd meshes onto faulty hypercubes using free dimension," IEEE Transactions on Computers, 43(5): 608-613, 1994.
[139] Computer programs are avaliable at http://algorithm.csie.ncku.edu.tw/pancyclicity/