完全雙分圖中不含C4飽和子圖的探討

The study of C4-saturated bipartite graphs

林泰平(Tai-Ping Lin)

指導教授 ： 高金美

淡江大學/理學院/數學學系碩士班/碩士(2006年)

https://doi.org/10.6846/TKU.2006.00629

摘要

如果圖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)中所含的一些元素。

關鍵字

圖 ； 雙分圖 ； 不含C4的飽和圖

並列摘要

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).

並列關鍵字

graph ； bipartite graph ； C4-saturated

參考文獻

of extremal Boolean matrices, Comput. Artif. Intell. 10

[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.