臺灣博碩士論文加值系統

　　連結網路為連結多個處理器的架構，hypercube與Star網路皆為常見的架構方式，也有許多相關研究以這兩種架構為主軸。容錯性質亦為很重要的研究主題，尤其是處於連結網路上的處理器數量很多時，在此篇論文中，我們將研究hypercube與其它bipartite圖形上的容錯性質，主要探討處理器之間連線故障的情形。
　　在這篇論文中，我們介紹漢米爾頓連通圖形和強的k邊漢米爾頓圖形，且我們提出建構可容錯的k邊漢米爾頓圖形和可雷斯漢米爾頓圖形的方式。我們研究一種漢米爾頓容錯圖形，稱為強的k邊漢米爾頓圖形，我們也針對強的k邊漢米爾頓圖形提出(k+2)-連接和K2笛卡兒乘積兩種建構方式，應用這些建構方式，我們可建構出更多新的強的k邊漢米爾頓圖形。

　　An interconnection network is the structure that connects the processors of parallel computer. The hypercube and star networks are the most fundamental topologies for interconnection networks. There are many researches based on these two topologies. Fault tolerance is also an important issue especially when the number of processors that in the interconnection network is large. In this thesis, we study the fault tolerance properties in hypercube and other bipartite graphs. We major in link failures.
　　In this thesis, we introduce the Hamiltonian graphs and k-edge Hamiltonian graphs. Furthermore, we present construction schemes for strongly k-edge Hamiltonian graphs and Hamiltonian laceable graphs. We present two construction schemes for strongly k-edge Hamiltonian graphs. These two schemes are (k+2)-join and Cartesian product with K2. Applying these schemes, we can construct more new strongly k-edge Hamiltonian graphs.

iii 中文摘要
iv ABSTRACT
v 誌謝
vii Contents
viii List of Figures
1 Chapter 1 Introduction and definitions
5 Chapter 2 Construction Scheme for strongly k-edge Hamiltonian graphs
5 2.1 Strongly k-edge Hamiltonian graphs and (k+2)-join operation
7 2.2 Strongly k-edge Hamiltonian graphs and Cartesian product operation
16 Chapter 3 The (k-1)-edge hyper Hamiltonian laceable graph is strongly k-edge Hamiltonian Graph
19 Chapter 4 Conclusions and future works
20 References
21 Experience

[1] C. N. Hung, X. S. Zhu, Construction for Strongly k-Hamiltonian Graphs, proceedings of the 19th Workshop on Combinatorial Mathematics and Computation Theory (2002), p. 17-22.
[2] M. Lewinter, W. Widulski, Hyper-Hamilton laceable and caterpillar-spannable product graphs, Comput. Math. Appl. 34 (1997), p. 99-104.
[3] T. K. Li, J. J. M. Tan, L. H. Hsu, Hamiltonian laceability on edge fault star graph, Parallel and Distributed Systems (2002), Proceedings. Ninth International Conference, p. 23-28.
[4] G. Simmons, Almost all n-dimensional rectangular lattices are Hamilton laceable, Congr. Numer. 21 (1978), p. 103-108.
[5] C. H. Tsai, J. J. M. Tan, T. Liang, L. H. Hsu, Fault-tolerant Hamiltonian laceability of hypercubes, Information Processing Letters 83 (2002), p. 301-306.
[6] S. Y. Hsieh, G. H. Chen, C. W. Ho, Hamiltonian —laceability of star graphs, Networks 36 (2000), p. 225-232