令Ck代表含有k個點的迴圈。假設G為一個圖且G中不包含子圖Ck，若連接圖G中任意不相鄰的兩點後，所形成的圖就會包含子圖Ck，那我們就稱圖G為Ck飽和圖。
    在本論文中，我們對於n點Ck飽和圖提出4種建構法，分別利用完全圖Kk-1之建構法、完全圖Kk/2+1或完全圖K(k+1)/2之建構法、迴圈Ck+1與完全圖Kk-4之建構法及擬似輪圖W(n, k) 之建構法得到n點Ck飽和圖，進而比較所獲得之四種n點Ck飽和圖的邊數。

Let Ck be a cycle with k edges. Let G be a graph. If there is no k-cycle contained in G and connecting any non-adjacent vertices of G will obtain a k-cycle, then we call G is a Ck saturated graph. 
    In this thesis, we give four constructions to construct a Ck saturated graph with n vertices. Respectively, we use the complete graph Kk-1, complete graphs Kk/2+1and K(k+1)/2, a (k+1)-cycle Ck+1 and a complete graph Kk-4, and a Wheel graph W(n, k) to construct a Ck saturated graph with n vertices. After that we enumerate the edges in each Ck saturated graph with n vertices and compare the numbers of edges of these four Ck saturated graphs with n vertices.

目      錄
誌謝辭．．．．．．．．．．．．．．．．．．．．．．．ⅱ
中文摘要．．．．．．．．．．．．．．．．．．．．．．ⅲ
英文摘要．．．．．．．．．．．．．．．．．．．．．． Ⅳ
目    錄．．．．．．．．．．．．．．．．．．．．Ⅵ
圖表目 錄．．．．．．．．．．．．．．．．．．．．Ⅷ
第一章  簡介…………………………………………………………… 1

第二章  預備知識……………………………………………………… 4

第三章	Ck飽和圖及建構法…………………………………………... 10
3-1	第一類建構法………………………………………………... 12
3-2	第二類建構法………………………………………………... 16
3-3	第三類建構法………………………………………………... 19
3-4	第四類建構法………………………………………………... 21

第四章	總結…………………………………………………………… 34

參考書目………………………………………………………………… 36




圖表目錄
表1-1………………………………………………………………………2
圖2.1…………………………………………………………….4、5、6、8
圖2.2……………………………………………………………………… 5
圖2.3……………………………………………………………………….6
圖2.4  K4完全圖………………………………………………………..7、8
圖2.5………………………………………………………………………..8
圖2.6………………………………………………………………………..9
圖2.7………………………………………………………………………..9
圖2.8  4點C4飽和圖…..…………………………………………………...9
圖3.1………………………………………………………………………10
圖3.2………………………………………………………………………10
圖3.3………………………………………………………………………11
圖3.4………………………………………………………………………11
圖3.5………………………………………………………………………11
圖3.6………………………………………………………………………12
圖3.7………………………………………………………………………13
圖3.8………………………………………………………………………14
圖3.9………………………………………………………………………15
圖3.10……………………………………………………………………..15
圖3.11……………………………………………………………………..17
圖3.12……………………………………………………………………..17
圖3.13……………………………………………………………………..20
圖3.14……………………………………………………………………..21
圖3.15……………………………………………………………………..22
圖3.16……………………………………………………………………..24
圖3.17……………………………………………………………………..25
圖3.18……………………………………………………………………..27
圖3.19……………………………………………………………………..28
圖3.20……………………………………………………………………..29
圖3.21……………………………………………………………………..31
圖3.22……………………………………………………………………..33
表4-1 C10 飽和圖之邊數  ……………………………………………..….34

參考書目

[1] Barefoot, C.A., Clark, L.H., Entringer, R.C., Porter, T.D., Szekely, L.A., Tuza, Zs. Cycle-saturated graphs of minimum size, Discrete Math.150(1996) 31-48.
[2] Bollobas, B., On a conjecture of Erdos, Hajnal and Moon, Amer. Math. Monthly, 74 (1967) 178-179.
[3] Bollobas, B., Extremal Graph Theory, Academic Press Inc. (1978).
[4] Bollobas, B., Extremal Graph Theory. In Handbook of Combinatorics (R.L. Graham, M. Grotschel and L. Lovasz, eds), North-Holland, (1995) 1231-1292.
[5] Bondy, J.A. Variations on the hamiltonian theme, Canad. Math. Bull. 15 (1972) 57-62
[6] Chen, Y.C., C5-saturated graphs, J. Graph Theory, 61, 2 (2009) 111-126.
[7] Clark, L.H., Crane, R.P., Entringer, R.C., Shapiro, H.D., On smallest maximally nonhamiltonian graphs, Congress. Numer. 53 (1986) 215-220.
[8] Clark, L.H., Entringer, R.C., Smallest maximally nonhamiltonian graphs, Period. Math. Hungar. 15 (1983) 57-68.
[9] Clark, L.H., Entringer, R.C., Shapiro, H.D., Smallest maximally nonhamiltonian graphs Ⅱ, Graphs Combin. 8 (1992) 225-231.
[10] Erdos, P., Hajnal, A. and Moon, J.W., A problem in graph theory, Amer. Math. Monthly 71 (1964) 1107-1110.
[11] Frick, M., Singleton, J., Lower bound for the size of maximal nontraceable graphs. Electron. J. Combin. 12 (2005), Research paper 32, 9 pp.
[12] Gould, R. Luczak, T. and Schmitt, J., Constructive Upper Bounds for Cycle-Saturated Graphs of Minimum Size, Electron. J. of Combin. 13(2006), #R29.
[13] Kaszonyi, L. and Tuza, Z., Saturated graphs with minimal number of edges, J. Graph Theory 10 (1986) 203-210.
[14] Lin, X., Jiang, W., Zhang, C., Yang, Y., On smallest maximally nonhamiltonian grphs, Ars Combinatoria 45 (1997) 263-270.
[15] Ollmann, L.T., K2,2-saturated graphs with a minimal number of edges, Proc. 3rd SouthEast Conference on Combinatorics, Graph Theory and Computing, (1972) 367-392.
[16] Tuza, Z., C4-saturated graphs of minimum size, Acta Universitatis Carolinae Mathematica et Physica 30 (1989) 2, 161-167.