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