Ck飽和圖的探討

The study of Ck-saturated graphs

李志偉(Chih-Wei Lee)

指導教授 ： 高金美

淡江大學/理學院/中等學校教師在職進修數學教學碩士學位班/碩士(2013年)

https://doi.org/10.6846/TKU.2013.00439

摘要

令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飽和圖的邊數。

關鍵字

完全圖 ； 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.

並列關鍵字

complete graphs ； Ck saturated graph

參考文獻

[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).

[5] Bondy, J.A. Variations on the hamiltonian theme, Canad. Math. Bull. 15 (1972) 57-62

[8] Clark, L.H., Entringer, R.C., Smallest maximally nonhamiltonian graphs, Period. Math. Hungar. 15 (1983) 57-68.