不含 K2,2 的二分極圖

機構典藏 > College of Sciences > Graduate Institute & Department of Mathematics > Thesis > Item 987654321/87462

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

Title:	不含 K2,2 的二分極圖
Other Titles:	Extremal K2,2-free bipartite graphs
Authors:	賴尚欣;Lai, Shang-Hsin
Contributors:	淡江大學中等學校教師在職進修數學教學碩士學位班高金美;Fu, Chin-Mei Kau
Keywords:	Zarankiewicz問題;極圖;二分圖;導出子圖;圖的分割;Zarankiewicz problem;extremal graph;bipartite graph;graph decomposition
Date:	2012
Issue Date:	2013-04-13 11:09:42 (UTC+8)
Abstract:	一個不含 K_2,2 的二分極圖是一個含有最多邊數且不含有子圖 K_2,2 的二分圖。若此二分圖為 K_m,n 的子圖，則求此二分極圖的邊數的問題也就是出名的Zarankiewicz 問題。在本論文中，我們令f(m,n)為 K_m,n 中不含 K_2,2 的二分極圖的邊數。我們獲得以下的結果： ①f(m,n)≤n/2+√(mn(m-1)+n^2/4) ②若 n≥(m\|2)，則 f(m,n)=(m\|2)+n。 ③若 m≡1,3 (mod 6)，則 K_m 恰可分割成 m(m-1)/6 個邊相異的 K_3 子圖，且f(m,n)=(m\|2)。 ④若 ((m\|2))/3≤n≤(m\|2)，則 f(m,n)=[((m\|2)+3n)/2] 。 ⑤若 m≡1,4 (mod 12)，則 K_m 恰可分割成 m(m-1)/12 個邊相異的 K_4 子圖，且，f(m,n)=2(m\|2)/3。 An extremal K_2,2-free bipartite graphs is a bipartite graph which contains the maximum number of edges and does not contain any subgraph K_2,2. If this bipartite graph is a subgraph of K_m,n, then finding the number of edges of the extremal bipartite graph is the well-known Zarankiewicz Problem. In this thesis, we let f(m,n) be the number of edges of the extremal K_2,2-free bipartite graph which is a subgraph of K_m,n. We obtain the following results: ①f(m,n)≤n/2+√(mn(m-1)+n^2/4) ②If ≥(m\|2), then f(m,n)=(m\|2)+n. ③If m≡1,3 (mod 6), then K_m decompose into (m(m-1))/6 edge-disjoint K_3 subgraphs, and f(m,n)=(m\|2). ④If ((m\|2))/3≤n≤(m\|2), then f(m,n)=[((m\|2)+3n)/2] . ⑤If m≡1,4 (mod 12), then K_m decompose into (m(m-1))/12 edge-disjoint K_4 subgraphs, and f(m,n)=2(m\|2)/3.
Appears in Collections:	[Graduate Institute & Department of Mathematics] Thesis

Files in This Item:

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

Loading...