# 臺灣博碩士論文加值系統

(3.231.230.177) 您好！臺灣時間：2021/08/04 05:51

:::

### 詳目顯示

:

• 被引用:0
• 點閱:63
• 評分:
• 下載:0
• 書目收藏:0
 假設圖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 的最小整數值。
 Let G be a graph. If there is no 4-cycle contained in G and connecting any nonadjacent 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 C4saturated graphs with n vertices, respectively.In this thesis, we obtain a construction of C4 saturated graph with n points, andgive 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; and2. 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 .
 目 錄第一章 簡介 ………………………………1第二章 基本定義 …………………………3第三章 含有n個點的C4飽和圖 …………8第四章 多分圖的C4飽和圖 ……………23參考書目 ……………………………………34
 參 考 書 目[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]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.Comput. (5) (1996) 29-33.[7]Z.Furedi, New asymptotics for bipartite Turan numbers, J. Combin. Theory Ser. A 75 141-144.[8]I. Reiman, Uber ein Problem von K. Zarankiewicz, Acta Math. Acad. Sci. Hungar. 9(1958),269-278[9]L. T. Ollmann,K2,2 saturated graphs with a minimal number of edges, In: F. Hoffman, R. B. Levow and R.S.D. Thomas, eds., Proc. 3rd Southeasten Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Florida (1972) 367-392.[10]Z. Tuza, C4-saturated graphs of minimum size, Acta Univ. Carolin. - Math. Phys. 30(1989)161-167.[11]Yang Yuansheng and P. Rowlinson,On extremal graphs without four-cycles, utilitas Mathematica 41(1992), 204-220.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 4-迴圈裝填圖的探討 2 不含 K_2,2 的二分極圖 3 非負矩陣之非負平方根 4 高中數學排列組合單元教材內容分析 5 國中數學九年級教科書相似形之內容分析 6 完全圖分割成迴圈與星圖的探討 7 不含K_2,3的二分極圖 8 車多項式 9 從食品安全檢驗與動植物防疫檢疫措施協定論臺美牛肉議定書之爭議 10 圖的拉普拉斯特徵值之探討 11 簡約圖譜矩陣理論與其應用 12 具有最大無符號拉普拉斯譜半徑的圖及其相關主題之研究 13 民眾與專家對於食品安全風險感知差異性及食品安全管理風險溝通之研究 14 完全雙分圖之星林分解數的探討 15 C4光合基因轉殖水稻的氣體交換能力及C4光合酵素活性之分析

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室