對於互連網路，由另一個網路的模擬問題已被塑造為的一個網路的嵌入(embedding)問題。因為迴圈(路徑)是在平行和分散式計算中設計低通信費用的最根本的網路。因此尋找特定長度的迴圈(路徑)，近年來受到了很多注意。
k元N立方體，是一個最常見的互連網路。在這篇論文，我們研究大部份有關k元N立方體的一些拓撲特性。在k元N立方體中，給予二個任意不同的兩個節點x和y，我們將證明，存在每一條長度是介於[k/2]n 與k^n−1從x到y的路徑，其中n>=2 是整數且k>=3是一個奇整數。根據這個結果，我們進一步證明k元N立方體中的每個邊(egde)會埋置於在每一條長度是介於k 與k^n的迴圈。另外，我們也證明k元N立方體是雙泛連結(bipanconnected)和邊-雙泛圓(edge-bipancyclic)，其中n>=2是整數且k>=2 是一個偶整數。

For interconnection networks, the problem of simulating one network by another is modelled as a network embedding problem. For finding a cycle (path) of given length, has received a great deal of attention in recent years because the cycle (path) is the most fundamental network for parallel and distributed computation which is suitable for designing simple algorithms with low communication costs.
The k-ary n-cube, denoted by Q^k_n, has been one of the most common interconnection networks. In this dissertation, we study most of the topological panconnectivity properties of Q^k_n. Given two arbitrary distinct vertices x and y in Q^k_n, we show that there exists an x-y path of every length from [k/2]n to k^n−1, where n>=2 is an integer and k>=3 is an odd integer. Based on this result, we further show that each edge in Q^k_n lies on a cycle of every length from k to k^n. In addition, we show that Q^k_n is both bipanconnected and edge-bipancyclic, where n>=2 is an integer and k>=2 is an even integer.

[1] S. G. Akl, Parallel computation: “Models and methods”, Prentice Hall, NJ, 1997.
[2] B. Alspach, D. Hare, “Edge-pancyclic block-intersection graphs”, Discrete Math. vol. 97, pp. 17–24, 1991.
[3] T. Araki and Y. Shibata, “Pancyclicity of recursive circulant graphs”, Information Processing Letters, vol. 81, pp. 187–190, 2002.
[4] T. Araki, “Edge-pancyclity of recursive circulants”, Inform. Process. Lett., vol. 88, pp. 287-292, 2003.
[5] N. Ascheuer, “Hamiltonian Path Problems in the On-Line Optimization of Flexible Manufacturing Systems”, PhD thesis, University of Technology, Berlin, Germany, 1995 (also available from h ftp://ftp.zib.de/pub/zib-publications/reports/TR-96-03.psi).
[6] Y. A. Ashir and I. A. Stewart, “Embeddings of cycles, meshes and tori in faulty k-ary n-cubes”, Proceedings of the 1997 International Conference on Parallel and Distributed Systems (ICPADS’97), IEEE computer society, pp. 429-435, 1997.
[7] Y. A. Ashir and I. A. Stewart, “Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes”, SIAM Journal on Discrete Mathematics, vol. 15, pp. 317–328, 2002.
[8] Avizienis, A., “Fault tolerant computing- an pverview”. IEEE Transations on Computers, vol. 4, pp. 5-8, 1971.
[9] M. M. Bae and B. Bose, “Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes”, IEEE Transactions on Computers, vol. 52, pp. 1271–1284, 2003.
[10] L. N. Bhuyan, and Dharma P. Agrawal,“Generalized Hypercube and Hyperbus Structures for a Computer Network,” IEEE Transactions on Computers, vol. c-33, no. 4, April 1984.
[11] E. van Blanken, J. van den Heuvel, and H. J. Veldman, “Pancyclicity of Hamiltonian line graphs,” Discrete Mathematics, vol. 138, no. 1-3, pp. 379-385, 1995.
[12] S. Borkar, R. Cohn, G. Cox, S. Gleason, T. Gross, H. T. Kung, M. Lam, B. Moore, C. Peterson, J. Pieper, L. Rankin, P.S. Tseng, J. Sutton, J. Urbanski, and J. Webb, “iWarp: an integrated solution to high-speed parallel computing,” Proceedings of the 1988 ACM/IEEE conference on Supercomputing, pp. 330–339, 1988.
[13] B. Bose, B. Broeg, Younggeun Kwon, and Y. Ashir, “Lee distance and topological properties of k-ary n-cubes,” IEEE Transactions on Computers, vol. 44, no. 8, pp. 1021–1030, 1995.
[14] M. Y. Chan and S. J. Lee. “Distributed fault-tolerant embeddings of rings in hypercubes,” Jurnal of Parallel and Distributed Computing, vol. 11, pp. 63-71, 1991.
[15] M. Y. Chang and S. J. Lee. “Fault-tolerant cycle-embedding in alternating group graphs,” Applied Mathematics and Computation, vol. 197, pp. 760-767, 2008.
[16] J. M. Chang and S. J. Yang. “On the existence of Hamiltonian circuits in faulty hypercubes,” SIAM Journal on Discrete Mathematics, vol. 4, no. 4, pp. 511–527, 1991.
[17] J. Chang, J. Yang, and Y. Chang, “Panconnectivity, fault-Tolorant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs”, Networks, vol. 44, no. 4, pp. 302–310, 2004.
[18] Y. C. Chen, L. H. Hsu, and Jimmy J. M. Tan, “A recursively construction scheme for super fault-tolerant hamiltonian graphs,” Applied Mathematics and Computation, vol. 177, no. 2, pp. 465-481, 2006.
[19] Y. C. Chen, C. H. Tsai, L. H. Hsu, J. J. M. Tan, “On some super fault-tolerant Hamiltonian graphs,” Applied Mathmatics and Computation, vol. 148, no. 3, pp. 729–741, 2004.
[20] W. S. Chiue and B. S. Shieh, “On connectivity of the Cartesian product of two graphs,” Applied Mathematics and Computation, vol. 102, no. 2-3, pp. 129–137, 1999.
[21] K. Day and A. E. Al-Ayyoub, “The cross product of interconnection networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 2, pp. 109–118, 1997.
[22] K. Day and A. E. Al-Ayyoub, “Fault diameter of k-ary n-cube Networks,” IEEE Transactions on Parallel and Distributed Systems, vil. 8, no. 9, pp. 903–907, 1997.
[23] K. Day and A. E. Al-Ayyoub, “Minimal fault diameter for highly resilient product networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 11, no. 9, pp. 926–930, 2000.
[24] K. Efe and A. Fernandez, “Products of networks with logarithmic diameters and fixed degree,” IEEE Transactions on Parallel and Distributed Systems, vol. 6, no. 9, pp. 963–975, 1995.
[25] T. El-Ghazawi and A. Youssef, “A generalized framework for developing adaptive fault-tolerant routing algorithms,” IEEE Transactions on Reliability, vol. 42, no. 2, pp. 250–258, 1993.
[26] Esfahanian, A. H., and Hakimi, S. L., “Fault-tolerant routing in thde Bruijn communication networks”. IEEE Transations on Computers,vol. 34, no. 9, pp. 777-788, 1985.
[27] J. Fan, X. Lin, and X. Jia, “Node-pancyclicity and edge-pancyclicity of crossed cubes”, Information Processing Letters, vol. 93, pp. 133-138, 2005.
[28] Jung-Sheng Fu, “Fault-tolerant cycle embedding in hierachial cubic networks,” Networks, vol. 43, no. 1, pp. 28-38, 2004.
[29] Jung-Sheng Fu, “Fault-tolerant cycle embedding in the hypercube,” Parallel Comptuing, vol. 29, no. 6, pp. 821-832, 2003.
[30] Jung-Sheng Fu, “Conditional fault-tolerant Hamiltonicity of star graphs,” Parallel computing, vol. 33, no. 7-8, pp. 488–496, 2007.
[31] Jung-Sheng Fu, “Fault-free Hamiltonian cycles in twisted cubes with conditional link faults,” Theoretical Computer Science, vol. 407, no. 1-3, pp. 318-329, 2008.
[32] E. Ganesan and D.K. Pradhan, “The hyper-de Bruijn multiprocessor networks: scalable versatile architecture,” IEEE Transactions on Parallel and Distributed Systems, vol. 4, no. 9, pp. 962-978, 1993.
[33] S. A. Ghozati and H. C. Wasserman, “The k-ary n-cube network: Modeling, topological properties and routing strategies”, Computers and Electrical Engineering, vol. 25, pp. 155–168, 1995.
[34] S. A. Ghozati and H.C. Wasserman, “The k-ary n-cube network: modeling, topological properties and routing strategies,” Computers and Electrical Engineering, pp. 1271-1284, 2003.
[35] F. Harary, “Conditional connectivity”. Networks, vol. 13, pp. 347–357, 1983.
[36] F. Harary, Graph Theory, Addison-Wesley, Massachusetts, 1972.
[37] S. Y. Hsieh and N. W. Chang,“ Hamiltonian path embedding and pancyclicity on the M¨obius cube with faulty nodes and faulty edges”, IEEE Transactions on Computers, vol. 55, pp. 854–863, 2006.
[38] S. Y. Hsieh and C. H. Chen, “Pancyclicity on M¨obius cubes with maximal edge faults”, Parallel Computing, vol. 30, pp. 407–421, 2004.
[39] S. Y. Hsieh and G. H. Chen, and C. W. Ho. Fault-free hamiltonian cycles in faulty arrangemenet graphs. IEEE Transations on Parallel and Distributed Systems, vol. 10, no. 3, pp. 223-237, 1999.
[40] S. Y. Hsieh and G. H. Chen, and C. W. Ho. “Longest fault-free paths in star graphs with edge faults”. IEEE Transations on Computers, vol. 50, no. 9, pp. 960-971, 2001.
[41] S. Y. Hsieh and T. J. Lin, “Embedding cycles and paths in a k-ary n-cube”, Proceedings of the 13th International Conference on Parallel and Distributed Systems (ICPADS), IEEE Computer Society, vol. 1, pp. 1–7, 2007.
[42] S. Y. Hsieh, T. J. Lin, and H. L. Huang, “Panconnectivity and edge-pancyclicity of 3-ary N-cubes”, Journal of Supercomputing, vol. 42, pp. 233–255, 2007.
[43] S. Y. Hsieh, T. J. Lin, and H. L. Huang, “Cycle and Path Embedding on 5-ary N-cubes”, RAIRO-Theor. Inf. Appl. vol. 43, pp. 133-144, 2009.
[44] S. Y. Hsieh and T. J. Lin, “Panconnectivity and Edge-Pancyclicity of k-Ary N-Cubes” , Networks, accepted to be published, 2008.
[45] S. Y. Hsieh, C. W. Ho, and G. H. Chen, “Fault-free Hamiltoninan cycles in faulty arrangement graphs,” IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 3, pp. 223–237, 1999.
[46] S. Y. Hsieh and C. Y. Wu, “Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults,” Journal of Combinatorial Optimization, in Press.
[47] H. C. Hsu, L. C. Chiang, J. J. M. Tan, and L. H. Hsu, “Fault hamiltonicity of augmented cubes,” Parallel Computing, vol. 31, no. 1, pp. 131–145, 2005.
[48] 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, vol. 42, no. 4, pp. 189–201, 2003.
[49] H. C. Hsu, T. K. Li, J. J. M. Tan, and L. H. Hsu, “Fault hamiltonicity and fault hamiltonian connectivity of the arrangment graphs,” IEEE Transactions on Computers, vol. 53, no. 1, pp. 39–52, 2004.
[50] C. N. Hung, H. C. Hsu, K. Y. Liang, and L. H. Hsu, “Ring embedding in faulty pancake graphs,” Information Processing Letters, vol. 86, pp. 271–275, 2003.
[51] W. T. Huang, Y.C. Chuang, J. M. Tan, and L. H. Hsu, “Fault-free Hamiltonain cycle in faulty M¨obius cubes,” Computaci¨on Sistemas, vol. 4, no. 2, pp. 106–114, 2000.
[52] W. T. Huang, Y. C. Chuang, J. 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, vol. E85A, no. 6, pp. 1359–1370, 2002.
[53] W. T. Huang, J. M. Tan, C. N. Hung, L. H. Hsu, “Fault-tolerant Hamiltonicity of twisted cubes,” Journal of Parallel and Distribute Computing, vol. 62, no. 4, pp. 591–604, 2002.
[54] 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, no. 24, pp. 5664–5674, 2007.
[55] S. C. Ku, B. F. Wang, and, T. K. Hung, “Constructing edge-disjoint spanning trees on product networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 3, pp. 213-221, 2003.
[56] F. T. Leighton, Introduction to parallel algorithms and architecture:“ arrays· trees· hypercubes”, Morgan Kaufmann, San Mateo, CA, 1992.
[57] Y. R. Leu and S. Y. Kuo, “Distributed Fault-tolerant ring embedding and reconfiguration in hypercubes.” IEEE Transation on ComputersI, vol. 48, no. 1, pp. 81-88, 1999.
[58] C. K. Lin, T. Y. Ho, J. J. M. Tan, and L. H. Hsu, “Fault-tolerant hamiltonicity and faulttolerant hamiltonian connectivity of the folded Petersen cube networks,” International Journal of Computer Mathematics, vol. 86, no. 1, pp. 57–66, 2009.
[59] M. Ma, G. Liu, and J.-M. Xu, “Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes”, Parallel Computing, vol. 33, pp. 36–42, 2007.
[60] M. Kouider and A. Marczyk, “On pancyclism in hamiltonian graphs,” Discrete Mahematics, vol. 251, no. 1-3, pp. 119-127, 2002.
[61] M. Ma and J. M. Xu, “Panconnectivity of locally twisted cubes,” Applied Mathematics Letters, vol. 19, pp. 673–677, 2006.
[62] W. Oed, “Massively parallel processor system CRAY T3D,” Technical Report, Cray
Research GmbH, Nov. 1993.
[63] S. Ohring and D. H. Hohndel, “Optimal fault tolerant communication algorithms on product networks using spanning trees,” Proceedings of Sixth IEEE Symposium on Parallel and Distributed Processing, pp. 188–195, 1994.
[64] J.-H. Park, “Panconnectivity and edge-pancyclicity of faulty recursive circulant G(2m, 4)”, Theoretical Computer Science, vol. 390, pp. 70–80, 2008.
[65] 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.
[66] J.-H. Park, H.-S. Lim, and H.-C. Kim, “Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements,” Theortical Computer Science, vol. 377, no. 1-3, pp. 170-180, 2007.
[67] A. L. Rosenberg, “Product-shuffle networks: towards reconciling shuffles and butterflies,” Discrete Applied Mathematics, vols. 37/38, pp. 465–488, 1992.
[68] H. Sarbazi-Azad, M. Ould-Khaoua, L. M. Mackenzie, and S. G. Akl, “On some properties of k-ary n-cubes”, Proceedings of the Eighth International Conference on Parallel and Distributed Systems (ICPADS), IEEE Computer Society, pp. 517–524, 2001.
[69] C. L. Seitz et al., “Submicron systems architecture project semi-annual technical report,” Technical Report Caltec-CS-TR-88-18, California Institute of Technology, Nov. 1988.
[70] Y. Sheng, F. Tian, and B. Wei, “Panconnectivity of locally connected claw-free graphs”, Discrete Mathematics, vol. 203, no. 1, pp. 253–260, 1999.
[71] Z. M. Song and Y. S. Qin, A new sufficient condition for panconnected graphs, Ars Combinatoria, vol. 34, pp. 161-166, 1992.
[72] C.-H. Tsai, “Linear array and ring embeddings in conditional faulty hypercubes,” Theortical Computer Science, vol. 314, no. 3, pp. 431–443, 2004.
[73] 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.
[74] Deqiang Wang, Tong An, Mingyang Pan, Kelun Wang, and Shuyan Qu, “Hamiltonian-like properies of k-Ary n-Cubes”, in Proceedings of Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT05), pp. 1002–1007,
2005.
[75] 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, no. 12, pp. 1747–1762, 2002.
[76] W.-W. Wang, M. Ma, and J.-M. Xu, “Fault-tolerant pancyclicity of augmented cubes”, Information Processing Letters, vol. 103, pp. 52-56, 2007.
[77] 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, no. 3, pp. 165–183, 2005.
[78] J. M. Xu, “Topological Structure and Analysis of Interconnection Networks”, Kluwer Academic Publishers, Dordrecht/Boston/London, 2001.
[79] J.-M. Xu, Z. Du, and M. Xu, “Edge-fault-tolerant edge-bipancyclicity of hypercubes”, Information Processing Letters, vol. 96, pp. 146-150, 2005.
[80] J.-M. Xu and M. Ma, “Cycles in folded hypercubes”, Applied Mathematics Letters, vol. 19, pp. 140–145, 2006.
[81] J.-M. Xu, M. Ma, and Z. Du, “Edge-fault-tolerant properties of hypercubes and folded hypercubes,” Australasian Journal of Combinatorics, vol. 35, pp. 7–16, 2006.
[82] J.-M. Xu, M. Ma, and M. L¨u, “Paths in M¨obius cubes and crossed cubes,” Information Processing Letters, vol. 97, pp. 94–97, 2006.
[83] M. Xu, X.-D. Hu, and J.-M. Xu, “Edge-pancyclicity and hamiltonian laceability of balanced hypercubes,” Applied Mathematics and Computation, vol. 189, pp. 1393–1401, 2007.
[84] M. Xu and J.-M. Xu,“ Edge-pancyclicity of M¨obius cubes,” Information Processing Letters, vol. 96, pp. 136-140, 2005.
[85] Ming-Chien Yang, Jimmy J.M. Tan, and Lih-Hsing Hsu, Hsieh, “Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes,” Journal of Parallel and Distributed Computing, vol. 67, no. 4, pp. 362–368, 2007.
[86] M. C. Yang, T. K. Li, J.M. Tan, and L. H. Hsu. “Fault-tolerant cycle-embedding of crossed cubes. ” Information Processing Letters,, vol. 88, no. 4, pp. 149–154, 2003.