Ck飽和圖的探討

機構典藏 > College of Sciences > Department of Applied Mathematics and Data Science > Thesis > Item 987654321/94015

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/94015

Title:	Ck飽和圖的探討
Other Titles:	Study of Ck-saturated graphs
Authors:	李志偉;Lee, Chih-Wei
Contributors:	淡江大學中等學校教師在職進修數學教學碩士學位班高金美;Kau Fu, Chin-Mei
Keywords:	完全圖;Ck飽和圖;complete graphs;Ck saturated graph
Date:	2013
Issue Date:	2014-01-23 13:47:44 (UTC+8)
Abstract:	令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.
Appears in Collections:	[Department of Applied Mathematics and Data Science] Thesis

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	575	View/Open

Loading...