完全雙分圖中不含C4飽和子圖的探討

淡江大學機構典藏 > 理學院 > 應用數學與數據科學學系 > 學位論文 > Item 987654321/32902

請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/32902

題名:	完全雙分圖中不含C4飽和子圖的探討
其他題名:	The study of C4-saturated bipartite graphs
作者:	林泰平;Lin, Tai-ping
貢獻者:	淡江大學數學學系碩士班高金美;Kau, Chin-mei
關鍵詞:	圖;雙分圖;不含C4的飽和圖;graph;bipartite graph;C4-saturated
日期:	2006
上傳時間:	2010-01-11 02:57:02 (UTC+8)
摘要:	如果圖G中不含C4，但再增加一邊之後就會產生C4，則稱圖G是不含C4的飽和圖。圖G為在Km,n中不含C4的飽和子圖，即表示圖G為Km,n的子圖，且為不含C4的飽和圖。在此篇論文中，主要是討論在Km,n中不含C4飽和子圖的可能邊數。我們令S(m,n)＝{t︱存在G為在Km,n中不含C4的飽和子圖，且︱E(G)︱＝t}，利用組合設計中之史坦納三元系及Bryant和Fu論文中判別圖G是否為含有最多邊的不含C4的飽和圖的建構法，而獲得當n足夠大時S(m,n)的最大值，及m≡0,1,2,3(mod 6)時S(m,n)的最大值。當1≦m≦6時，獲得S(m,n)的所有元素，進而建構出一些在Km,n中不含C4的飽和子圖，產生S(m,n)中所含的一些元素。 A C4-saturated graph is a graph G which contains no C4,but when adding any edge in G will results C4.A C4-saturated bipartite graph in Km,n is a subgraph G of Km,n and G is a C4-saturated graph.In this thesis,we consider the possible number of edges of C4-saturated bipartite graphs in Km,n .We define S(m,n)＝{t｜there exists a graph G which is a C4-saturated bipartite graph in Km,n with t edges}.By using the Steiner triple system in combinatorial designs and the construction in the paper of Bryant and Fu which showed that a maximum C4-saturated bipartite graph in Km,n ,we obtain the maximum value of S(m,n) when n is large or m≡0,1,2,3(mod 6).After that,we obtain the spectrum of S(m,n) when 1≦m≦6.We get some elements in S(m,n).
顯示於類別:	[應用數學與數據科學學系] 學位論文

文件中的檔案:

檔案	大小	格式	瀏覽次數
	0Kb	Unknown	265	檢視/開啟

在機構典藏中所有的資料項目都受到原著作權保護.

TAIR相關文章

資料載入中.....