不含 K_2,2 的二分極圖

一個不含 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。

關鍵字

Zarankiewicz問題；極圖；二分圖；導出子圖；圖的分割

並列摘要

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.

並列關鍵字

Zarankiewicz problem ； extremal graph ； bipartite graph ； graph decomposition

參考文獻

[1] Bollobes, B., “Extremal Graph Theory,” Academic Press, New York, 1978.

[3] Culik, K., Teilwesise Losung eines verallgemeinerten Problems von Zarankiewicz, Anna. Soc. Polon. Math. 3 (1956), 165-168.

[4] Goddard, W., M.A. Henning and O.R. Oellermann, Bipartite Ramsey numbers and Zarankiewicz numbers, Discrete Math. 219 (2000), 85-89.

[5] Griggs, J., and H. Chih-Chang, On the half-half case of the Zarankiewicz problem, Discrete Math. 249 (2002), 9-104.

[6] Griggs, J., and J. Ouyang, (0,1)-Matrices with no half-half submatrix of ones, European J. Combinatorics 18 (1997), 751-761.

國際替代計量

不含 K_2,2 的二分極圖

全文下載

主題瀏覽