§ 瀏覽學位論文書目資料
  
系統識別號 U0002-2006200803004500
DOI 10.6846/TKU.2008.00637
論文名稱(中文) 完全圖分割成4-迴圈太陽圖之探討
論文名稱(英文) The decomposition of complete graphs into sun graphs of 4-cycle
第三語言論文名稱
校院名稱 淡江大學
系所名稱(中文) 數學學系碩士班
系所名稱(英文) Department of Mathematics
外國學位學校名稱
外國學位學院名稱
外國學位研究所名稱
學年度 96
學期 2
出版年 97
研究生(中文) 邱群博
研究生(英文) Cyun-Bo Ciou
學號 695190206
學位類別 碩士
語言別 繁體中文
第二語言別
口試日期 2008-06-06
論文頁數 33頁
口試委員 指導教授 - 高金美
委員 - 高金美
委員 - 江南波
委員 - 黃文中
關鍵字(中) 完全二分圖
完全圖
4-迴圈
太陽圖
分解
關鍵字(英) complete bipartite graph
complete graph
4-cycle
sun graph
decomposition
第三語言關鍵字
學科別分類
中文摘要
當一個含有n個點的圖中,任兩點都有邊相連,我們稱此圖為完全圖,記為K_(n)。當一個圖中的點集合可以分成兩個非空的集合V_(1)及V_(2),若 V_(1)中的每一點都與V_(2)中的點有邊相連,且在V_(1)及V_(2)中的點都沒有邊相連,則稱此圖為完全二分圖;若 V_(1)中有m個點,V_(2)中有n個點,則此完全二分圖記為K_(m,n)。假設 v_(1), v_(2), v_(3), v_(4)為4-迴圈C_(4)的依序四個頂點,在 C_(4)外面加入4個點w_(1), w_(2), w_(3), w_(4)及4條邊 {v_(i), w_(i) }, 1≦ i≦ 4,所形成的圖稱為C_(4)的太陽圖,記為S(C_(4))。在本篇論文中,我們證明了
(1) 當m≧ n≧ 4, n≠ 5, 且若n= 4則m不為4k+2形態時,完全二分圖K_(m,n)能分割成4-迴圈太陽圖的充分必要條件為m×n為8的倍數,(2) 完全圖K_(n)能分割成4-迴圈太陽圖的充分必要條件為n≡ 0 或1 (mod 16)。
英文摘要
A graph with n vertices satisfies that every two vertices are connected by an edge, then we call this graph a complete graph with n vertices, denoted by K_(n). If the vertex set of a graph can be partitioned into two disjoint nonempty sets V_(1) and V_(2) , every vertex in V_(1) connects every vertex in V_(2) and there is no edge in V_(1) and V_(2), then we call this graph is a complete bipartite graph. If V_(1) contains m elements and V_(2) contains n elements, then we denote this complete bipartite graph K_(m,n). Let {v_(1), v_(2), v_(3), v_(4)} be the vertex set of a 4-cycle C_(4). If we add another four vertices w_(1), w_(2), w_(3), w_(4) and four edges {v_(i), w_(i)}, 1≦ i≦ 4 to C_(4), then we call this graph a sun graph of C_(4), denoted by S(C_(4)). In this thesis, we proved that 
(1) if m≧ n≧ 4, n≠ 5, and if n= 4 then m is not the form of 4k+2, the complete bipartite graph K_(n,m) can be decomposed into sun graphs of 4-cycle (S(C_(4))) if and only if mn is a multiple of 8,  and 
(2) the complete graph K_(n) can be decomposed into sun graphs of 4-cycle (S(C_(4))) if and only if n≡ 0, 1 (mod 16).
第三語言摘要
論文目次
目錄
第一章 簡介..............................................................................................1
第二章 預備知識......................................................................................3
第三章 主要結果....................................................................................12
  第一節 Km,n可分割成S(C4)................................................................12
  第二節 Kn可分割成S(C4)..................................................................24
  第三節 Kn可循環分割成S(C4)..........................................................30
參考文獻..................................................................................................33
 
圖表目錄
圖2.1..........................................................................................................3
圖2.2..........................................................................................................4
圖2.3..........................................................................................................4
圖2.4..........................................................................................................5
圖2.5..........................................................................................................6
圖2.6..........................................................................................................7
圖2.7..........................................................................................................7
圖2.8..........................................................................................................8
圖2.9..........................................................................................................9
圖2.10.......................................................................................................10
圖2.11.......................................................................................................11
圖3.1.........................................................................................................13
圖3.2.........................................................................................................14
圖3.3.........................................................................................................16
圖3.4.........................................................................................................18
圖3.5.........................................................................................................21
圖3.6.........................................................................................................25
圖3.7.........................................................................................................26
圖3.8.........................................................................................................27
圖3.9.........................................................................................................28
圖3.10.......................................................................................................30
圖3.11.......................................................................................................31
圖3.12.......................................................................................................32
參考文獻
參考文獻
[1] B. Alspach and H. Gavlas,  Cycle decompositions of Kn and Kn – I, J. Combin. Theory Ser. B., 81, no.1,(2001), 77-99.
[2] E. J. Billington, D.G. Hoffman, Decomposition of complete tripartite graphs into gregarious 4-cycles. Discrete Math, 261(2003)87-111.
[3] F. Buckley, M. Lewinter, A friendly introduction to graph theory. Prentice Hall, 2003.
[4] M. Buratti, A. Del Fra, Existence of cyclic k-cycle system of the complete graph. Discrete Math, 261(2003)113-125.
[5] Wei-Hung Lee, Decompose complete tripartite graph into asteroidal graph. Tamkang University, 2007.
[6] D. B. West, Introduction to graph theory 2nd Ed. Prenfice Hall, 1996, 2001.
論文全文使用權限
校內
校內紙本論文立即公開
同意電子論文全文授權校園內公開
校內電子論文立即公開
校外
同意授權
校外電子論文立即公開

如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信