臺灣博碩士論文加值系統

在這篇論文當中，我們介紹超立方體圖形在相鄰點容錯之後，有Property 2H以及Hamiltonian laceable的性質。依據這些定理，我們可以在超立方體圖形中建構沒有錯點錯邊的最長環狀；此環的長度為2n-2|Fv|+4，而它的容錯最多到n個任意點。我們也可以建構沒有錯點錯邊的最長路徑，而路徑的容錯最多到n-1的任意點。

In this paper, we show that the adjacency fault tolerance for property 2H of hypercube. We also show that the adjacency fault tolerance for Hamiltonian laceability of hypercube. Applying these results, we can construct a fault-free cycle with length at least 2n-2|Fv|+4 in Qn-Fv where Fv is the faulty vertices set contains at least two black vertices and two white vertices with |Fv|n. We also construct a fault-free path of length at least 2n-2|Fv|+3 between two different color vertices, and construct the fault-free path with of length at least 2n-2|F_v|+2 between two same color vertices, |Fv| n-1.

Chapter 1　Introduction　......................................1
Chapter 2　Preliminaries　.....................................4
Chapter 3　The adjacency property 2H of hypercube　............6
Chapter 4 The adjacency Hamiltonian laceable of hypercube ...15
Chapter 5 The Longest ring in faulty hypercube　.............27
Section 5.1. Hamiltonian cycle ............................27
Section 5.2. Fault-free cycle ............................ 28
Chapter 6 The Longest path in faulty hypercube...............30
Section 6.1. between two different colorvertice ...........30
Section 6.2. between two same color vertice ...............32
Chapter 7 Conclusion　.......................................36
References ................................................ ..37

[1] J. S. Fu, ”Fault-tolerant cycle embedding in the hypercube,” Parallel Computing,,vol. 29, pp.821-832, (2003).
[2] S. Y. Hsieh, ”Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges,” Parallel Computing, vol. 32, pp.84-91, (2006).
[3] C. N. Hung, Y. H. Chang, and C. M. Sun, ”LONGEST PATHS AND CYCLES
IN FAULT HYPERCUBES,” Proceedings of the IASTED ICPDCN, pp.101-110,(2006).
[4] C. D. Park and K. Y. Chwa, ”Hamiltonian properties on the class of hypercube-like networks,” Information Processing Letters,,vol. 91, pp.11-17, (2004).
[5] Abhijit Sengupta, ”On ring embedding in hypercubes with faulty nodes and links,” Information Processing Letters,, vol. 68, pp.207-214, (1998).
[6] C. H. Tsai, J.J.M. Tan, T.Liang, and L.H. Hsu, ”Fault-tolerant Hamiltonian laceability of hypercubes,” Information Processing Letters,, vol. 83, pp.301-306,(2002).
[7] Y. C. Tseng, ”Embedding a ring in a hypercube with both faulty links and faulty nodes,” Information Processing Letters,, vol. 59, pp.217-222, (1996).
[8] S.B. Akers, B. Krishnamurthy, ”A group-theoretic model for symmetric interconnection networks,” IEEE Trans. Comput,, vol. 38(4), pp.555-566,(1989).
[9] Y. H. Chang, C. N Hung, ”Adjacent Vertices Fault Tolerance Hamiltonian Laceability of Hypercube Graphs,” Workshop on Combinatorial Mathematics and Computation Theory, vol 22, pp.301-309, (2005).
[10] J.C. Bermond(Ed.), ”Interconnection networks,” Discrete Appl. Math,,pp.37+38 ,(1992).
[11] F. Buckley, F. Harary, ”Distance in Graphs,” Addison-Wesley,,(1990).
[12] M. Y. Chen, S.-J. Lee, ”Distributed fault-tolerant embedding of rings in hypercubes,” Parallel Distrib. Comput,, vol. 11 p.63-71, (1991).
[13] J.H. Chang, C.S. Shin, K.Y. Chwa, ”Ring embedding in faulty star graphs,”IEICE Trans. Fund,, E82-A (9), pp.1953-1964, (1999).
[14] D.F. Hsu, ”Interconnection Networks and Algorithms,”Networks,, vol. 23 (4),(1993).
[15] S. Y. Hsieh, ”Embedding longest fault-free paths onto star graphs with more vertex faults,” Theoretical Computer Science,, vol. 337, pp.370-378,(2005).
[16] S.Y. Hsieh, G.H. Chen, C.W. Ho, ”Embed longest rings onto star graphs with vertex faults,” Proceedings of the International Conference on Parallel Processing,, pp.140-147, (1998).
[17] S.Y. Hsieh, G.H. Chen, C.W. Ho, ”Fault-free Hamiltonian cycles in faulty arrangement graphs,” IEEE Transactions on Parallel and Distributed Systems,, vol.10(3), pp.223-237, (1999).
[18] S.Y. Hsieh, G.H. Chen, C.W. Ho, ”Hamiltonian-laceability of star graphs,” Networks,, vol. 36, pp.225-232, (2000).
[19] S.Y. Hsieh, G.H. Chen, C.W. Ho, ”Longest fault-free paths in star graphs with vertex faults,” Theoret. Comput. Sci,, vol. 262, pp.215-227, (2001).
[20] S.Y. Hsieh, G.H. Chen, C.W. Ho, ”Longest fault-free paths in star graphs with edge faults,” IEEE Trans. Comput,, vol. 50(9), pp.960-971, (2001).
[21] C.N. Hung and K.C. Hu, ”Fault-tolerant Hamiltonian laceability of bipartite hypercube-like networks,” The Proceedings of ICS, pp.1145-1149,(2004).
[22] F.T. Leighton, ”Parallel Algorithms and Architectures Arrays, Trees and Hypercubes,” Morgan Kaufmann, San Mateo,, (1992).
[23] S. Latifi, S.Q. Zheng, N. Bagherzadeh, ”Optimal ring embedding in hypercubes with faulty links,” Proceedings of the IEEE,, pp.178-184, (1992).
[24] J. H. Park, Hee-Chul Kim, ”Longest paths and cycles in faulty star graphs,”Parallel Distrib. Comput,, vol. 64, pp.1286-1296, (2004).
[25] Abhijit Sengupta, ”On ring embedding in hypercubes with faulty nodes and links,” Information Processing Letters,, vol. 68 , pp.207-214,(1998).
[26] G. Simmons, ”Almost all n-dimensional rectangular lattices are Hamilton laceable,” Congr. Numer,, vol. 21, pp.103-108, (1978).
[27] Y. Saad and M.H. Schultz, ”Topological properties of hypercubes, ” IEEE Trans,Comput,, vol. 37(7), pp.867-872, (1998).
[28] Y. C. Tseng, S.H. Chang, J.P. Sheu, ”Fault-tolerant ring embedding in stargraphs with both link and node failures,” IEEE Trans. Parallel Distributed Systems,, vol. 8(12), pp.1185-1195, (1997).
[29] C.H. Tsai, J.J.M. Tan, T. Liang, L. H. Hsu, ”Fault-tolerant Hamiltonian laceability of hypercubes,” Information Processing Letters,, vol. 83, pp.301-306, (2002)
[30] D.J. Wang, ”Embedding Hamiltonian cycles into folded hypercubes with linkfaults,” Journal of Parallel and Distributed Computing,, vol. 61(4), pp.545-564,(2001).
[31] P.J. Yang, S.B. Tien, C.S. Raghavendra, ”Embedding of rings and meshes onto faulty hypercubes using free dimensions,” IEEE Transactions on Computers,, vol.43(5), p.608-613, (1994).