淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1507201312400900
中文論文名稱 Ck飽和圖的探討
英文論文名稱 The study of Ck-saturated graphs
校院名稱 淡江大學
系所名稱(中) 中等學校教師在職進修數學教學碩士學位班
系所名稱(英) Executive Master's Program In Mathematics for Teachers
學年度 101
學期 2
出版年 102
研究生中文姓名 李志偉
研究生英文姓名 Chih-Wei Lee
學號 700190050
學位類別 碩士
語文別 中文
口試日期 2013-06-22
論文頁數 36頁
口試委員 指導教授-高金美
委員-李武炎
委員-顏經和
中文關鍵字 完全圖  Ck飽和圖 
英文關鍵字 complete graphs  Ck saturated graph 
學科別分類
中文摘要 令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.

論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2013-07-15公開。
  • 同意授權瀏覽/列印電子全文服務,於2013-07-15起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信