跳到主要內容

臺灣博碩士論文加值系統

(35.175.191.36) 您好!臺灣時間:2021/08/01 00:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:李志偉
研究生(外文):Chih-Wei Lee
論文名稱:Ck飽和圖的探討
論文名稱(外文):The study of Ck-saturated graphs
指導教授:高 金 美
指導教授(外文):Chin-Mei Kau Fu
口試委員:李武炎顏經和
口試日期:2013-06-22
學位類別:碩士
校院名稱:淡江大學
系所名稱:中等學校教師在職進修數學教學碩士學位班
學門:教育學門
學類:普通科目教育學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:中文
論文頁數:36
中文關鍵詞:完全圖Ck飽和圖
外文關鍵詞:complete graphsCk saturated graph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:58
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
令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.



QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top