設計一個最佳k容錯之號誌環網路相當於建造一個最佳k漢米爾頓連通圖, 其中k表示點或邊壞掉的個數. 對任意 $V_1 \subset V$, $E_1 \subset E$ 滿足 $\left| V_1 \right|+\left| E_1 \right| \leq k $ 的圖$G=(V,E)$ 被稱為k-漢米爾頓連通圖假如$G-(V_1-E_1)$是漢米爾頓連通圖.
在所有相同點數的k漢米爾頓連通圖裡面, 邊的點數最少的k漢米爾頓連通圖G*是最佳的.
在這篇論文中, 我們證明 是最佳k漢米爾頓連通圖其中k是大於等於4的偶正整數.

Designing an optimal $k$-fault-tolerant network for token rings is equivalent to constructing an optimal $k$-hamiltonian graph, where $k$ is a positive integer and corresponds to the number of faults.
A graph $G=(V,E)$ is $k$-hamiltonian if $G-(V_1-E_1)$ is
hamiltonian for arbitrary $V_1 \subset V$, $E_1 \subset E$ with
$\left| V_1 \right|+\left| E_1 \right| \leq k $. A
$k$-hamiltonian graph G* is optimal if it contains the fewest
edges among all $k$-hamiltonian graphs with the same number of
vertices as G*.
In this thesis, we prove that $G_{n,k}$ is optimal $k$-hamiltonian for $k$ an even integer greater than 4.

中文摘要
英文摘要
誌謝
目錄
圖目錄
第一章 Introduction and Definitions 5
第二章 $G_{n, k}$ is $k$-hamiltonian in Base Group 6
第三章 $G_{n,k}$ is $k$-hamiltonian,$n > 2k$ 12
第四章 Discussion 66

[1] J. Bruck, R. Cypher and C. T. Ho, Fault-tolerant
meshes and hypercubes with minimum numbers of spares, IEEE Trans. Comput. 42 (1993) 1089-1104.
[2] R. S. Chou and L. H. Hsu, 1-edge fault-tolerant design
for meshes, Parallel Processing Letters 4 (1994) 385-389.
[3] S. Dutt and J. P. Hayes, Designing fault-tolerant systems using automorphisms, J. Parallel and Distributed
Computing 12 (1991) 249-268.
[4] Douglas B. West, {\em Introduction to Graph Theory}(Prentice-Hall, Inc, 1996)
[5] R. Gould, {\em Graph Theory}(Benjanmin/Cummings,Menlo Park,CA,1988).
[6] F. Harary and J. P. Hayes, Edge fault tolerant in
graphs, Networks 23 (1993) 135-142.
[7] F. Harary and J. P. Hayes, Node fault tolerant in
graphs, Networks 27 (1996) 19-23.
[8] J. P. Hayes, A graph model for fault-tolerant
computing systems, IEEE Trans. Computers C25 (1976) 875-883.
[9] C. N. Hung, Optimal {\it k}-Fault-Tolerant Networks
for Token Rings, Dissertation in Computer and information
Science, National Chiao Tung University, R.O.C., (1999).
[10] H. K. Ku and J. P. Hayes, Optimally Edge fault
tolerant trees, Networks 27 (1996) 203-214.
[11] F. T. Leighton, Introduction to Parallel Algorithms
and Architectures: Arrays $\cdot$ Trees $\cdot$ Hypercubes,
Morgan Kaufmann Publishers, San Mateo, CA,1992.
[12] K. Mukhopadhyaya and B. P. Sinha, Hamiltonian graphs
with minimum number of edges for fault-tolerant topologies,
Information Processing Letter 44 (1992) 95-99.
[13] M. Paoli, W.W. Wong and C.K. Wong, Minimum {\it
k}-Hamiltonian graphs II, Journal of Grapg Theory 10 (1986)
79-95.
[14] C. J. Shih and K. E. Batcher, Adding multiple-fault tolerant togeneralixed cube networks, IEEE Trans. Parallel and Distributed Systems 5 (1994) 785-792.
[15] T. Y. Sung, M. Y. Lin, and T. Y. Ho,
Multiple-edge-fault tolerant with respect to hypercubes, IEEE
Trans. on Parallel and Distributed Systems 8 (1997) 187-192.
[16] T. Y. Sung, Academia Sinica, T. Y. Ho and L. H.
Hsu, Optimal {\it K}-Fault-Tolerant Networks for Token Rings, accepted by Journal of Information Science and Engineering.
[17] S. Y. Wang, L. H. Hsu and T. Y. Sung, Faithful
1-edge fault tolerant graphs, Information Processing Letter 61
(1997) 173-181.
[18] W.W. Wong and C.K. Wong, Minimum {\it
k}-Hamiltonian graphs, Journal of Grapg Theory 8 (1984)
155-165.