C4飽和圖的探討

The study of C4 saturated graph

洪明岳(Ming-Yueh Hung)

指導教授 ： 高金美

淡江大學/理學院/中等學校教師在職進修數學教學碩士學位班/碩士(2013年)

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

摘要

假設圖G 並不包含子圖C4，若在圖G 中任意不相鄰的兩點增加一邊後，就
會包含有子圖C4，那我們就稱圖G 為C4 飽和圖。令sat(n,C4)和ex(n,C4)分別代
表所有n 點C4 飽和圖中的邊數最小值與最大值。
在這篇論文中找到含有n 點C4 飽和圖的一種建構法，並給予含有n 點C4
飽和圖最少邊的一種建構法。再利用當n<=11 時C4 飽和圖的邊數之上、下界，
建構出其邊數介於sat(n,C4)和ex(n,C4)之間的n 點C4 飽和圖。接著應用圖的鄰接矩陣及C4 飽和圖的性質，利用Maple 判斷所產生的圖是否為C4 飽和圖。
我們定義了在完全多分圖中的C4 飽和圖，並探討完全多分圖Kn(m)的C4 飽
和圖中邊數最少的建構方式，得到以下結果：

1. sat(Kn,m, C4) <= m + n - 1，其中sat(Kn,m, C4) = min {│E(G)│: 圖G 為Kn,m 中C4 飽和圖}。
2. sat(Kn(m), C4) <= mn – 1 + ┌(n-2)/2┐*m, 其中sat(Kn(m), C4) = min {│E(G)│: 圖 G 為Kn(m) 中C4 飽和圖}，┌x┐為大於等於x 的最小整數值。

關鍵字

完全圖 ； 完全多分圖 ； C4飽和圖

並列摘要

Let G be a graph. If there is no 4-cycle contained in G and connecting any non
adjacent vertices of G will obtain a 4-cycle, then we call G is a C4 saturated graph.
Let sat(n, C4) and ex(n, C4) be the minimum and maximum number of edges of all C4
saturated graphs with n vertices, respectively.
In this thesis, we obtain a construction of C4 saturated graph with n points, and
give another construction of C4 saturated graph with minimum edge. For n <= 11, we give a C4 saturated graph with n vertices and q edges, for each q between sat(n, C4)
and ex(n, C4). After that, we use Maple to check whether the graph is a C4 saturated graph by using the adjacency matrix of a graph and the properties of C4 saturated graphs.
We define a C4 saturated graph in a complete multipartite graph Kn (m) and obtain the following results:

1. sat(Kn,m, C4) <= m + n - 1; and
2. sat(Kn(m), C4) <= mn – 1 + ┌(n-2)/2┐*m, where sat(K, C4) = min {|E(G)|: G is a C4 saturated graph in the graph K} and ┌x┐ is the smallest integer greater than x .

並列關鍵字

complete graph ； complete multipartite graph ； C4 saturated graph

參考文獻

[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]C. R. J. Clapham, A. Flockart, and J. Sheehan, Graphs without four-cycle, Journal of Graph Theory 13(1989), 29-47

[5] P. Erdos, A. Hajnal and J. W. Moon, A problem in graph theory, Amer. Math. Monthly71(1964) 1107-1110.

[6]Z. Furedi, An upper bound on Zarankiewwcz’ problem, Combin. Probab.