當一個圖形G 包含至多k 個錯誤邊並且每一個點都至少會連接兩個非錯誤邊的情況下，必定存在一條漢彌爾頓圓圈（Hamiltonian cycle），則我們稱這個圖形G 有條件式k 邊容錯漢彌爾頓性質(conditional k-edge-fault Hamiltonian)。
　　讓G和H為任意的兩個圖形，讓k1和k2分別代表δ(G)和δ(H)並且都大於3。假如圖G滿足漢彌頓連接性、(k1-2)邊容錯相鄰點漢彌爾頓連接性、條件式(2k1-5)邊容錯漢彌爾頓性質(Hamiltonian-connected、(k1-2)-edge-fault adjacency-Hamiltonian-connected、conditional (2k1-5)-edge-fault Hamiltonian)；而圖H滿足漢彌頓連接性、(k2-2)邊容錯相鄰點漢彌爾頓連接性、條件式(2k2-5)邊容錯漢彌爾頓性質。則我們可以證明卡氏積圖G×H將會滿足條件式(2k1+2k2-5)邊容錯漢彌爾頓性質。
　　根據這個結果，我們能應用在一個屬於卡氏積圖架構的多處理器系統：近似鄰居網狀超立方體(nearest neighbor mesh hypercube)，將其証明擁有不錯的條件式邊容錯漢彌爾頓性質。

　　A graph G is called conditional k-edge-fault Hamiltonian if after deleting at most k edges from G and each vertex is incident to at least two fault-free edges, the resulting graph remains Hamiltonian. Given two graph G and H, let k1 and k2 be the positive integers such that k1=δ(G)≧3, k2=δ(H)≧3. If G is Hamiltonian-connected, (k1-2)-edge-fault adjacency-Hamiltonian-connected, and conditional (2k1-5)-edge-fault Hamiltonian; H is Hamiltonian-connected, (k2-2)-edge-fault adjacency-Hamiltonian-connected, and conditional (2k2-5)-edge-fault Hamiltonian. Then, we show that the Cartesian product network G×H is (2k1+2k2-5)-edge-fault Hamiltonian. We then apply our result to determine the conditional edge-fault Hamiltonicity of one multiprocessor system, the nearest neighbor mesh hypercube, belong to Cartesian networks.

[1] S. G. Akl, Parallel Computation: Models and Methods, Prentice Hall, NJ, 1987.
[2] N. Bagherzadeh, Hamiltonian Path Problems in the On-Line Optimization of Flexible Manufacturing Systems, PhD thesis, University of Technology, Berlin, Germany, 1995 (also available from hftp://ftp.zib.de/pub/zib-publications/reports/TR-96-03.psi).
[3] Yaagoub Ashir, Iain A. Stewart, and Aqeel Ahmed, "Communication algorithms in k-ary n-cube interconnection networks," Information Processing Letters, vol. 16, no. 1, pp. 43-48, 1997.
[4] Yaagoub A. Ashir and Iain A. Stewart, "Fault-tolerant embeddings of hamiltonian circuits in k-ary n-cube," SIAM J. Discrete Math, vol. 15, no. 3, pp. 317-328, 2002.
[5] S. Bettayeb, "On the k-ary hypercube," Theoretical Computer Science, vol. 140, pp. 333-339, 1995.
[6] Laxmi N. Bhuyan and Dharma P. Agrawal, "Generalized Hypercube and Hyperbus Structures for a Computer Network", IEEE Transactions on Computers, vol. c-33, no. 4, pp. 323-333, 1984.
[7] M. Y. Chang and S. J. Lee, "On the existence of Hamiltonian circuits in faulty hypercubes," SIAM Journal on Discrete Mathematics, vol. 4, issue 4, pp. 511-527, 1991.
[8] 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.
[9] 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.
[10] K. Day and A. E. Al-Ayyoub, "Fault diameter of k-ary n-cube Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 8, issue 9, pp. 903-907, 1997.
[11] 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.
[12] K. Efe and A. Fernandez, "Products of networks with logarithmic diameters and ¯xed degree,"IEEE Transactions on Parallel and Distributed Systems, vol. 6, no. 9, pp. 963-975, 1995.
[13] 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.
[14] Jung-Sheng Fu, "Fault-tolerant cycle embedding in the hypercube," Parallel Comptuing, vol. 29, no. 6, pp. 821-832, 2003.
[15] Jung-Sheng Fu, "Conditional fault-tolerant Hamiltonicity of star graphs,"Parallel Comptuing, vol. 33, no. 7-8, pp. 488-496, 2007.
[16] 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.
[17] S. Y. Hsieh, C. W. Ho, and G. H. Chen, "Fault-free Hamiltoninan cycles in faulty arrangement graphs," Theoretical Computer Science, vol. 10, no. 3, pp. 223-237, 1999.
[18] S. Y. Hsieh and C. D. Wu, "Conditional Edge-Fault-Tolerant Hamiltonian Cycle Embedding of Star Graphs," in: Proceedings of the 13th International Conference on Parallel and Distributed Systems, 2007.
[19] S. Y. Hsieh and C. Y. Wu, "Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults," Journal of Combinatorial Optimization, doi:10.1007/s10878-008-9157-x.
[20] 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.
[21] 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.
[22] F. T. Leighton, Introduction to parallel algorithms and architecture: arrays, trees, hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
[23] 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.
[24] Jung-Heum Park, Hee-Chul Kim, and Hyeong-Seok 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.
[25] Jung-Heum Park, Hee-Chul Kim, and HHee-Chul Kim, "Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements," Theoretical Computer Science, vol. 377, issue 1-3, pp. 170-180, 2007.
[26] A. L. Rosenberg, "Product-shu²e networks: towards reconciling shu²es and butter°ies," Discrete Applied Mathematics, vol. 37/38, pp. 465-488, 1992.
[27] Chang-Hsiung Tsai, "Linear array and ring embeddings in conditional faulty hypercubes," Theoretical Computer Science, vol. 314, issue 3, pp. 431-443, 2004.
[28] Yu-Chee Tseng, Shu-Hui Chang, and Jang-Ping 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.
[29] Nen-Chung Wang, Chih-Ping Chu, and Tzung-Shi 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.
[30] Nen-ChungWang, Cheng-Pang Yen, and Chih-Ping Chu, "Multicast Communication in Wormhole-Routed Symmetric Networks with Hamiltonian Cycle Model," Journal of Systems Architecture, vol.
51, issue 3, pp. 165-183, 2005.