對一個網路拓樸結構而言，迴圈(cycle)的存在性有著相當多的討論和應用。若討論圖形中是否可以找到各種不同長度的迴圈，此問題就是泛迴圈(pancyclic)問題。有時候，希望在圖形中找到長度有特殊限制的迴圈。例如：討論圖形中是否可以找到各種不同的偶數長度之迴圈，此問題就是偶泛迴圈(bipancyclic)問題。以上兩個性質還有延伸成另外更加強大的性質：邊泛迴圈(edge-pancyclic)和邊偶泛迴圈(edge-bipancyclic)。一個圖形如果滿足邊泛迴圈，代表著圖形中每一個邊都會位於各種不同長度的迴圈。並且，一個圖形如果滿足邊偶泛迴圈，代表著圖形中每一個邊都會位於各種不同偶數長度的迴圈。

在一個運作中的網路拓樸中，故障是會隨時發生的。所以有許多研究便是在探討一個圖形是否具備良好的容錯能力。換言之，此問題是探討一個圖形在某些點或某些邊發生錯誤時，它是否仍然維持良好的圖形性質(如上面所提的泛迴圈性)。在本篇論文裡，我們將在卡氏積圖(Cartesian product graph)中討論有關泛迴圈性質的邊容錯問題。所謂的卡氏積圖，是將兩個不同的圖形經過卡氏積的運算建構起一個新圖形。而且，許多研究指出卡氏積圖會繼承原本兩個圖形一些良好的性質。而我們的結果証實了卡氏積圖會繼承下列良好的邊容錯之泛迴圈性質：泛迴圈性質、偶泛迴圈性質、邊泛迴圈性質、以及邊偶泛迴圈性質。

這些結果我們也証實它們的容錯結果是最佳的(optimal)，而且能被應用在以下兩者屬於卡氏積圖架構的多處理器系統：近似鄰居網狀超立方體(nearest neighbor mesh hypercubes)和廣義超立方體(generalized hypercubes)。証明了這兩個系統擁有各種邊容錯的泛迴圈性質。

For interconnection network, the existence of the cycle has many discussions and applications. The pancyclic problem involves testing whether or not a graph contains cycles of all possible lengths. Sometimes, the length of the desired cycle satisfies some conditions. For example, the bipancyclic problem involves testing whether or not a graph contains cycles of all possible even lengths. Edge-pancyclic property and edge-bipancyclic property are the extension of the above two properties. A graph is edgepancyclic if each edge of graph lies on a cycle of every possible length. And, a graph is edge-bipancyclic if each edge of graph lies on a cycle of every possible even length.

When a network is activated, the error may occur. Many studies discuss whether or not a graph has some good fault-tolerant properties. In other words, they discuss whether or not the graph still satisfies some good properties (for example, pancyclic property) when some vertices and edges are faulty. A Cartesian product graph is generated by applying the graph Cartesian product operation “ × ” to factor networks.
Previous studies have investigated the various topological properties of Cartesian product graph. In this dissertation, we investigate the fault-free cycle embedding problems with edge faults on the Cartesian product graph. Given two graphs, which satisfy some specific properties, the edge-fault pancyclic properties of Cartesian product of the two graphs are efficiently evaluated. Those pancyclic properties are pancyclicity, bipancyclicity, edge-pancyclicity, and edge-bipancyclicity.

We also show the obtained results are optimal for the number of faulty edges tolerated and those results are applied to two multiprocessor systems, the nearest neighbor mesh hypercubes and generalized hypercubes, both of which belong to Cartesian product graphs.

[1] S. B. Akers and B. Krishnamurthy : A group-theoretic model for symmetric interconnection
networks. In: Proceedings of the 1986 International Conference on
Parallel Processing, 216–223 (1989).
[2] S. G. Akl : Parallel Computation: Models and Methods. Prentice Hall, NJ (1987)
[3] M. Bae and B. Bose : Edge Disjoint Hamiltonian Cycles in k-Ary n-Cubes and
Hypercubes. IEEE Transactions on Computers, 52(10), 1271-1284 (2003)
[4] L. N. Bhuyan and D. P. Agrawal : Generalized hypercube and hyperbus structures
for a computer network. IEEE Transactions on Computers C-33(4), 323–333 (1984)
[5] Q. Y. Chang, M. J. Ma, and J. M. Xu : Fault-tolerant pancyclicity of locally
twisted cubes. Journal of University of Science and Technology of China 36(6),
607–610 (2006)
[6] Q. Y. Chang, M. J. Ma, and J. M. Xu : Fault-tolerant pancyclicity of twisted
cubes. Operation Research and Management Science 16(1), 52–57 (2007)
[7] J. M. Chang and J. S. Yang : Fault-tolerant cycle embedding in alternating group
graphs. Applied Mathematics and Computation 197(2), 760–767 (2008)
[8] A. Chapman, M. Nabi-Abdolyousefi, and M. Mesbahi : Controllability and Observability
of Network-of-Networks via Cartesian Products. IEEE Transactions on
Automatic Control 59(10), 2668-2679 (2014).
[9] M. Y. Chen and K. G. Shin : Processor allocation in an n-cube multiprocessor
using gray codes. IEEE Transactions on Computers c-36(12), 1396–1407 (1987).
[10] 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).
[11] W. S. Chiue and B. S. Shieh : On connectivity of the Cartesian product of two
graphs. Applied Mathematics and Computation 102(2-3), 129–137 (1999)
[12] K. Day and A. E. Al-Ayyoub : The cross product of interconnection networks.
IEEE Transactions on Parallel and Distributed Systems 8(2), 109–118 (1997)
[13] 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)
[14] K. Day and A. E. Al-Ayyoub : Minimal fault diameter for highly resilient product
networks. IEEE Transactions on Parallel and Distributed Systems 11(9), 926–930
(2000)
[15] K. Efe and A. Fernandez : Products of networks with logarithmic diameters and
fixed degree. IEEE Transactions on Parallel and Distributed Systems 6(9), 963–
975 (1995)
[16] A. El-Amawy and S. Latifi : Properties and performance of folded hypercubes.
IEEE Transactions on Parallel and Distributed Systems 2(3), 31–42 (1991).
[17] T. El-Ghazawi and A. Youssef : A general framework for developing adaptive
fault-tolerant routing algorithms. IEEE Transactions on Reliability 42(2), 250–
258 (1993)
[18] 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 55(7), 854–863 (2006)
[19] Z.A. Hussain, B. Bose , A. Al-Dhelaan : Generalized Hypercubes: Edge-
Disjoint Hamiltonian Cycles and Gray Codes. IEEE Transactions on Computers,
63(2),375–382 (2014)
[20] J. S. Jwo, S. Lakshmivarahan, and S. K. Dhall : A new class of interconnection
networks based on the alternating group. Networks 33, 315–326 (1993).
[21] R. E. Kessler and J. L. Schwarzmeier : Cray T3D: a new dimension for Cray
research. In Proceedings of the 38th IEEE Computer Society International Conference
pp. 176–182 (1993).
[22] Y. Kikuchi and T. Araki : Edge-bipancyclicity and edge-fault-tolerant bipancyclicity
of bubble-sort graphs. Information Processing Letters 100(2), 52–59 (2006)
[23] 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
14(3), 213–221 (2003)
[24] S. Latifi, S. Zheng , and N. Bagherzadeh : Optimal ring embedding in hypercubes
with faulty links. In: Twenty-Second International Symposium on Fault-Tolerant
Computing Symp, 178–184 (1992).
[25] 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).
[26] F. T. Leighton : Introduction to parallel algorithms and architecture: arrays,
trees, hypercubes. Morgan Kaufmann, San Mateo, CA (1992)
[27] 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).
[28] T. K. Li : Cycle embedding in star graphs with edge faults. Applied Mathematics
and Computation 167(2), 891–900 (2005)
[29] R. Li : A new sufficient condition for Hamiltonicity of graphs. Information Processing
Letters 98(4), 159–161 (2006)
[30] 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)
[31] J. Li, S. Wang, D. Liu, and S. Lin : Edge-bipancyclicity of the k-ary n-cubes with
faulty nodes and edges. Information Sciences 181(11), 2260–2267 (2011).
[32] T. J. Lin, S. Y. Hsieh, and Justie S. T. Juan : Embedding cycles and paths in product
networks and their applications to multiprocessor systems. IEEE Transactions
on Parallel and Distributed Systems, 23(6), 1081–1089, (2012).
[33] W. Najjar and J. L. Gaudiot : Network resilience: a measure of network fault
tolerance. IEEE Transactions on Computers 39, 174–181 (1990)
[34] S. Ohring and D. H. Hohndel : Optimal fault tolerant communication algorithms
on product networks using spanning trees. In: 6th IEEE Symposium on Parallel
and Distributed Processing, pp. 188–195 (1994)
[35] A. L. Rosenberg : Product-shuffle networks: towards reconciling shuffles and butterflies.
Discrete Applied Mathematics 37/38, 465–488 (1992)
[36] A. Sen, A. Sengupta, and S. Bandyopadhyay : On some topological properties of
hypercube, incomplete hypercube and supercube. In: Proceedings of the International
Parallel Processing Symposium, Newport Beach, April, 636–642 (1993).
[37] S. Sun, M. Xu, and K. Wang : Edge-fault-tolerant pancyclicity of arrangement
graphs. Information Sciences, DOI: 10.1016/j.ins.2014.06.046 (2014).
[38] C. H. Tsai : Linear array and ring embeddings in conditional faulty hypercubes.
Theoretical Computer Science 314(3), 431–443 (2004)
[39] P. Y. Tsai, G. H. Chen, and J. S. Fu : Edge-fault-tolerant pancyclicity of alternating
group graphs. Networks 53(3), 307–313 (2009).
[40] P. Y. Tsai and Y. T. Lin : Cycle embedding in alternating group graphs with faulty
elements. Advanced Technologies, Embedded and Multimedia for Human-centric
Computing. Springer Netherlands, 1281–1281 (2014).
[41] W. W. Wang, M. J. Ma, and J. M. Xu : Fault-tolerant pancyclicity of augmented
cubes. Information Processing Letters 103(2), 52–56 (2007)
[42] D.B. West : Introduction to Graph Theory (second edition). Prentice Hall, Upper
Saddle River, NJ (2001)
[43] Y. Xiang, I. A. Stewart : A Multipath Analysis of Biswapped Networks. Computer
Journal 54(6), 920–930 (2011)
[44] J. M. Xu: Topological structure and analysis of interconnection networks. Kluwer
academic publishers (2001).
[45] J. M. Xu, Z. Z. Du, and M. Xu : Edge-fault-tolerant edge-bipancyclicity of hypercubes.
Information Processing Letters 96(4), 146–150 (2005).
[46] J. M. Xu and M. J. Ma : Survey on path and cycle embedding in some networks.
Forntiers of Mathematics in China 4(2), 217–252 (2009).
[47] J. M. Xu, M. J. Ma, and Z. Z. Du : Edge-fault-tolerant properties of hypercubes
and folded hypercubes. Australasian Journal of Combinatorics 35, 7–16 (2006).
[48] M. Xu, X. D. Hu, and Q. Zhu : Edge-bipancyclicity of star graphs under edge-fault
tolerant. Applied Mathematics and Computation 183(2), 972–979 (2006).
[49] 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(4), 149–154 (2003)
[50] M. C. Yang, T. K. Li, J. J. M. Tan, and L. H. Hsu : On embedding cycles into
faulty twisted cubes. Information Sciences 176(6), 676–690 (2006)
[51] Y. Xiang and I. A. Stewart : Bipancyclicity in k-ary n-cubes with faulty edges under
a conditional fault assumption. IEEE Transactions on Parallel and Distributed
Systems 22(9), 1506–1513 (2011)
[52] M. C. Yang, J. 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).