系統識別號 | U0002-2007200601180600 |
---|---|
DOI | 10.6846/TKU.2006.00629 |
論文名稱(中文) | 完全雙分圖中不含C4飽和子圖的探討 |
論文名稱(英文) | The study of C4-saturated bipartite graphs |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 數學學系碩士班 |
系所名稱(英文) | Department of Mathematics |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 94 |
學期 | 2 |
出版年 | 95 |
研究生(中文) | 林泰平 |
研究生(英文) | Tai-Ping Lin |
學號 | 693150137 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2006-06-16 |
論文頁數 | 40頁 |
口試委員 |
指導教授
-
高金美
委員 - 傅恆霖 委員 - 周兆智 委員 - 高金美 |
關鍵字(中) |
圖 雙分圖 不含C4的飽和圖 |
關鍵字(英) |
graph bipartite graph C4-saturated |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
如果圖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). |
第三語言摘要 | |
論文目次 |
第一章 簡介 …………………………………… 1 第二章 預備知識 ……………………………… 5 第三章 Km,n中不含C4的飽和子圖最大和最小邊數12 第四章 Km,n中不含C4 的飽和子圖的邊數 …… 20 參考書目 ………………………………………… 38 附錄 ……………………………………………… 39 圖 表 目 錄 圖2.1,2.2 …………………………………… 5 圖2.3,2.4,2.5 ……………………………… 6 圖2.6 ………………………………………… 7 圖2.7 ………………………………………… 8 圖2.8,2.9 …………………………………… 9 圖2.10,2.11,2.12,2.13,2.14,2.15,2.16, 2.17,2.18 ……………………………… 10 圖3.1 ………………………………………… 14 圖3.2 ………………………………………… 17 圖3.3 ………………………………………… 19 表4.1,4.2,4.3 ……………………………… 27 圖4.4,4.5 …………………………………… 30 圖4.6,4.7 …………………………………… 31 圖4.8,4.9 …………………………………… 33 圖4.10,4.11 ………………………………… 34 圖4.12,4.13 ………………………………… 37 |
參考文獻 |
[1] A.E. Andreev, On an algebraic method for construction of extremal Boolean matrices, Comput. Artif. Intell. 10 (2) (1991) 99-109. [2] B. Bollobas, Extremal Graph Theory, Academic Press, New York, 1978. [3] D.E. Bryant and Hung-Lin Fu, C4-saturated bipartite graphs, Discrete Math. 259 (2002) 263-268. [4] Z. Furedi, An upper bound on Zarankiewicz’problem, Combin. Probab. Comput. (5) (1996) 29-33. [5] Z. Furedi, New asymptotics for bipartite Turan numbers, J. Combin. Theory Ser. A 75 141-144. [6] J.R. Griggs, Chih-Chang Ho, On the half-half case of the Zarankiewicz problem, preprint. [7] J.R. Griggs, Ouyang, (0,1)-matrices with no half-half submatrix of ones, European J. Combin. 18 (1997) 751- 761. [8] T.P. Kirkman, On a problem in combinations, Cambridge and Dublin Math. Journal, 2 (1847), 191-204. [9] K. Zarankiewicz, Problem p 101, Colloq. Math. 2 (1951) 301. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信