如果圖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.