完全二部圖中C4與C6飽和子圖的探討

淡江大學機構典藏 > 理學院 > 數學學系暨研究所 > 學位論文 > Item 987654321/102163

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/102163

题名:	完全二部圖中C4與C6飽和子圖的探討
其它题名:	The study of C4,C6-saturated bipartite graphs
作者:	張博淳;Chang, Po-Chun
贡献者:	淡江大學數學學系碩士班高金美;Kau, Chin-Mei
关键词:	Zarankiewicz問題;二部圖;C4與C6飽和圖;Zarankiewicz problem;bipartite graph;C4, C6-saturated graph
日期:	2014
上传时间:	2015-05-04 09:48:57 (UTC+8)
摘要:	一個C4與C6飽和二部圖是一個不含有C4與C6的二部圖，且加上任意不相鄰兩點的邊後會形成C4或C6。我們要探討的是一個C4與C6飽和二部圖的邊數為多少。在本論文中，我們令z(m, n)為二部圖Km,n的子圖中為C4與C6飽和圖的最多邊數，s(m, n)為最少邊數。我們獲得以下的結果： 1.s(m ,n)=m+n-1 2.∀n≥3，z(3, n)=n+2、∀n≥4，z(4, n)=n+4，∀n≥6，z(5, n)=n+6 3.若n≥⌊m^2/4⌋，則z(m,n)= ⌊m^2/4⌋+n 4.設 n≥⌊m^2/4⌋，若s(m ,n)≤ x ≤z(m ,n)，則在 K_(m,n) 中存在一個 C4與C6飽和圖其邊數為x。 A C4, C6-saturated bipartite graph is a bipartite graph if it contains no 4-cycle and 6-cycle, but joining any nonadjacent vertices produces a graph that does contain a 4-cycle or 6-cycle. We will find the number of edges of a C4, C6-saturated bipartite graph. We let z(m, n) be the maximum number of edges of a C4,C6-saturated bipartite graph in Km,n, and s(m, n) be the minimum number of edges of a C4, C6-saturated bipartite graph in Km,n. In this thesis, we obtains the following results： 1.s(m,n)=m+n-1 2.∀n ≥ 3, z(3, n) = n+2, ∀n≥4, z(4, n) = n+4, ∀n≥6, z(5, n)= n+6. 3.If n≥⌊m^2/4⌋,then z(m,n)= ⌊m^2/4⌋+n 4.Let n≥⌊m^2/4⌋. If s(m,n)≤ x ≤z(m,n), then there exists a subgraph of K_(m,n) which is a C4, C6-saturated graph, and the number of edges is x.
显示于类别:	[數學學系暨研究所] 學位論文

文件中的档案:

档案	大小	格式	浏览次数
index.html	0Kb	HTML	194	检视/开启

在機構典藏中所有的数据项都受到原著作权保护.

TAIR相关文章

数据加载中.....