一個連結網路(interconnection network)的基本拓樸(topology)通常用一個圖型(graph)G = (V, E)表示，其中V表示節點(vertex)集合，E表示邊(edge)集合。假設一個圖G能夠嵌入任意長度的k-迴圈(k-cycle)且迴圈長度範圍介於3 ≤ k ≤ |V(G)|我們稱此圖G為泛圈(pancyclic)；假設一個圖G能夠嵌入任意偶數長度的k-迴圈且迴圈長度範圍介於4 ≤ k ≤ |V(G)|，我們稱此圖G為泛偶圈(bipancyclic)。
超立方體(hypercube)是一個廣受歡迎的網路，已經被廣泛地應用在平行系統上，並且有許多良好的網路拓樸性質，例如正則性(regularity)、小直徑(small diameter)、強度連通性(strong connectivity)、遞迴建構(recursive construction)、分割能力(partition ability)、相對低連結複雜度(relatively low link complexity)、簡易路由與廣播演算法(easy routing and broadcasting algorithms)等。
在連結網路中迴圈嵌入(cycle embedding)是很熱門的一個研究問題，因為它是一個重要測量工具，用來決定網路中的拓樸結構是否可嵌入各種不同長度的迴圈並加以應用。此外，在網路中嵌入不同長度的迴圈能夠有利於並行程序的執行效率，曾有許多文獻討論嵌入各種長度迴圈。在本研究中，我們在多維度的超立方體網路(n-dimensional hypercube network)Qn中，令邊e為 Qn 的任意一條邊，在本研究中我們討論在超立方體 Qn 上經過邊e的簡單k-迴圈數量，其k = 4、6、8。

The underlying topology of an interconnection network is usually modeled as a graph G = (V,E), in which V is the vertex set and E is the edge set. A graph G is pancyclic if any k-cycle can be embedded into it for 3 ≤ k ≤ |V(G)|; G is bipancyclic if any k-cycle of even length can be embedded into it for 4 ≤ k ≤ |V(G)|.
The hypercube is a popular network and it has been widely used in parallel systems. It also has many attractive properties, including regularity, symmetry, small diameter, strong connectivity, recursive construction, partition ability, relatively low link complexity, and easy routing and broadcasting algorithms.
The cycle embedding problem is one of the most popular research issues in interconnection networks, because it is an important measurement for determining whether the topology of a network is suitable for an application in which embedding rings of various lengths into the topology is required. Moreover, embedding cycles of different sizes into a network are benefit to execute parallel programs efficiently. There are many literatures which discussing cycle embedding of various lengths. Let edge e be any edge of the hypercube Qn . In this proposal, we discuss the number of simple k-cycles, which passing through the edge e for k = 4, 6, and 8 in the hypercube Qn .

摘要 ................................................... i
Abstract .............................................. ii
Contents .............................................. iii
List of Figures ....................................... iv
Chapter 1. Introduction ............................... 1
Chapter 2. Hypercubes ................................. 4
Chapter 3. Main Result ................................ 7
Chapter 4. Conclusions ................................ 25
References ............................................ 26

[1] J. A. Bondy and U. S. R. Murty, "Graph theory with applications", North Holland, New York, (1980).
[2] L. Bhuyan and D. P. Agrawal, "Generalized hypercube and hypercubes structures for a computer network," IEEE Transactions on Computers 33, pp. 323-333(1984)
[3] G. G. Cash, "The number of n-cycles in a graph," Applied Mathematics and Computation 184, pp. 1080-1083 (2007).
[4] Y. C. Chang and H. L. Fu, "The number of 6-cycles in a graph," Bulletin of the ICA 39, pp. 27-30 (2003).
[5] X. B. Chen, "Hamiltonian paths and cycles passing through a prescribed path in hypercubes," Information Processing Letters 110, pp. 77-82 (2009).
[6] H. Ding and Z. Huang, "Isomorphism identification of graphs: Especially for the graphs of kinematic chains," Mechanism and Machine Theory 44, pp. 122-139 (2009).
[7] Q. Dong and X. Yang, "Embedding a long faulty-free cycle in a crossed cube with more faulty vertices," Information Processing Letters 110, pp. 464-468 (2010).
[8] T. Dvorák, "Hamiltonian cycles with prescribed edges in hypercubes," SIAM Journal of Discrete Mathematics 19, pp. 135-144 (2005).
[9] J. Fan, X. Lin, Y. Pan and X. Jia, "Optimal fault-tolerant embedding of paths in twisted cubes," Journal of Parallel and Distributed Computing 67, pp. 205-214 (2007).
[10] J. Fan and Y. Xiao, "A method of counting the number of cycles in LDPC codes," International Conference of Signal Processing 3, pp. 2183-2186 (2006).
[11] F. F. Fang, "The bipancycle-connectivity of the hypercube," Information Sciences 178, pp. 4679-4687 (2008).
[12] J. F. Fang, "The bipancycle-connectivity of the hypercube, " Information Sciences 178, pp. 4679-4687 (2008).
[13] F. Harary and B. Manvel, "On the number of cycles in a graph," Mathematica Slovaca 21, pp. 55-63 (1971).
[14] L. Hongmei, "Cycles in enhanced hypercube networks," International Seminar on Future Information Technology and Management Engineering , pp. 560-563 (2008).
[15] 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, pp. 41-43 (2009).
[16] S. Y. Hsieh, C. N. Kuo and H. L. Huang, "1-vertex-fault-tolerant cycles embedding on folded hypercubes," Discrete Applied Mathematics 157, pp. 3094-3098 (2009).
[17] S. Y. Hsieh and J. Y. Shiu, "Cycle embedding of augmented cubes," Applied Math- ematics and Computation 191, pp. 314-319 (2007).
[18] H. S. Hung, J. S. Fu and G. H. Chen, "Fault-free Hamiltonian cycles in crossed cubes with conditional link faults," Information Sciences 177, pp. 5664-5674 (2007)
[19] Y. R. Leu and S. Y. Kuo, "Distributed fault-tolerant ring embedding and reconguration in hypercubes," IEEE Transactions on Computers 48, pp. 81-88 (1999).
[20] T. K. Li, C. H. Tsai, Jimmy J. M. Tan, and L. H. Hsu, "Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes," Information Processing Letters 87, pp. 107-110 (2003).
[21] M. Ma and B. Liu, "Cycles embedding in exchanged hypercubes," Information Processing Letters 110, pp. 71-76 (2009).
[22] David F. Robinson, Dan Judd Philip K. Mckinley and Betty H. C. Cheng, "Efficient multicast in all-port wormhole-routed hypercubes," Journal of Parallel and Distributed Computing 31, pp. 126-140 (1995).
[23] Y. Saad and M. H. Schultz, "Topological properties of hypercubes," IEEE Transac-tions on Computers 37 (7), pp. 867-872 (1988).
[24] C. Troncoso, B. Gierlichs, B. Preneel, and I. Verbauwhede, "Perfect matching disclosure attacks," Privacy Enhancing Technologies–8th International Symposium, PETS 2008 5134, pp. 2-23 (2008).
[25] C. H. Tsai, "Fault-free cycles passing through prescribed paths in hypercubes with faulty edges," Applied Mathematics Letters 22, pp. 852-855 (2009).
[26] X. Wu, M. He, F. Wang, J. Yang, and S. Latify, "Distinct paths for the star graph," International Conference on Communications and Mobile Computing, pp. 322-326 (2009).
[27] P. J. Wan, "TWDM multichannel lightwave hypercube networks," Theoretical Computer Science 194, pp. 123-136 (1998).
[28] D. Xiang, "Unicast-based fault-tolerant multicasting in wormhole-routed hypercubes," Journal of Systems Architecture 54, pp. 1164-1178 (2008).
[29] J. M. Xu and M. Ma, "Cycles in folded hypercubes," Applied Mathematics Letters 19, pp. 140-145 (2006).
[30] M. Xu, X. D. Hu, and J. M. Xu, "Edge-pancyclicity and Hamiltonian laceability of the balanced hypercubes," Applied Mathematics and Computation 189, pp. 1393-1401 (2007).
[31] M. Xu and J. M. Xu, "Edge-pancyclicity of Möbius cubes," Information Processing Letters 96, pp. 136-140 (2005).
[32] M. C. Yang, "Edge-fault-tolerant node-pancyclicity of twisted cubes," Information Processing Letters 109, pp. 1206-1210 (2009).