(3.236.6.6) 您好！臺灣時間：2021/04/22 19:05

### 詳目顯示:::

:

• 被引用:0
• 點閱:63
• 評分:
• 下載:0
• 書目收藏:0
 一個具有n個點的圖中，若任意兩點皆有邊相連，我們稱此圖為n個點的完全圖，記作Kn。一個具有n個點的連通圖，其每一點的度數皆為2，我們稱此圖為n-迴圈，記作Cn。一個具有n+1個點的連通圖，其中有一點的度數為n，其餘各點的度數皆為1，我們稱此圖為星圖，記作Sn，同構於K1,n。設G為一個簡單圖，G1,G2,…,Gt為G的子圖，若滿足下列條件： (1) E(G1)∪E(G2)∪ ... ∪E(Gt) = E(G)； (2) 對於1 ≦ i ≠ j ≦ t，E(Gi) ∩ E(Gj) = 空集合，則稱G可分割為G1,G2,…,Gt，記作G = G1+ G2+ … + Gt。若H是G的子圖，且G1,G2,…,Gt都與H同構，則稱G可分割成t個H，記為G = tH。若G可分割成p個G1與q個G2，則記為G = pG1 + qG2。　 在本論文中，我們證明了：(1) 當n≡0 (mod 6)，Kn可分割成C3和S3的各種組合。(2) 當n≡1 (mod 6)，Kn可分割成C3和S3的各種組合。進而得到以下定理定理：當n≡1,3 (mod 6)，n ≧ 3且p、q為非負整數。 如果Kn可分割成p個C3和q個S3， 若且唯若p + q = n(n-1)/6 且q ≠ 1,2。
 A complete graph Kn is a graph with n vertices and there is an edge joining any two vertices. An n-cycle Cn is a connected graph with n vertices and the degree of each vertex is 2. A star graph Sn is a graph with n+1 vertices and there is a vertex of degree n, the others are degree of 1. Let G be a simple graph and G1,G2,…,Gt be subgraphs of G. If E(G1)∪E(G2)∪…∪E(Gt) = E(G) and for all 1≦ i ≠ j ≦t，E(Gi)∩E(Gj) = empty set, then we call that G can be decomposed into G1, G2, … , Gt, denoted by G = G1+ G2+ … + Gt. If G1, G2, … , Gt are isomorphic to graph H, then we call G can be decomposed into H. If G can be decomposed into p copies of G1 and q copies of G2, that G can denoted by G = pG1 + qG2. In this paper, we show that:(1) if n≡1 (mod 6), then Kn can be decomposed into C3 and S3.(2) if n≡3 (mod 6), then Kn can be decomposed into C3 and S3.Combining the above results, we obtain the following theorem:Theorem: n≡1, 3 (mod 6), n≧3. For any nonnegative integers p and q.Kn can be decomposed into p copies of C3 and q copies of S3 if and only if p + q = n(n-1)/6 and q ≠ 1, 2。
 目 錄第一章　簡介 ……………………………………………………… 01第二章　預備知識 ………………………………………………03第三章 Kn分割成C3和S3 ……………………………16 第一節 n≡1(mod 6) ……………………………32 第二節 n≡3(mod 6) ……………………………41第四章　結論 ……………………………………………………… 45參考文獻 ……………………………………………………………… 46圖目錄圖2.1 G ………………………………………………………………… 03圖2.2 H為G的子圖…………………………………………………… 03圖2.3 連通圖G1和非連通圖G2 ……………………………………04圖2.4 deg(v)=3 ………………………………………………………… 04圖2.5 C4 ………………………………………………………………………… 05圖2.6 K5 ………………………………………………………………………… 05圖2.7 K2,3 ………………………………………………………………… 06圖2.8 S4 ………………………………………………………………………… 07圖2.9 K5= C5＋C5 = 2C5………………………………………… 08圖2.10 G H…………………………………………………………………… 08圖3.1 K4 = 1C3 + 1S3 ………………………………………… 17圖3.2 M1 ………………………………………………………………………… 24圖3.3 M1 ………………………………………………………………………… 25圖3.4 W1 ………………………………………………………………………… 26圖3.5 W1 = 6S3…………………………………………………………… 26圖3.6 M2 ………………………………………………………………………… 26圖3.7 K15 = K2 ∪ K2,13 ∪ K13 …………………… 29圖3.8 有洞的交換擬似群的建構STS的方法……………… 31圖3.9 G ………………………………………………………………… 32圖3.10 G ………………………………………………………………… 33圖3.11 對應於x1°x2=x4，x1°x3=x2所形成的圖W …35圖3.12 G …………………………………………………………………………… 37圖3.13 G …………………………………………………………………………… 38圖3.14 G …………………………………………………………………………… 39圖3.15 對應於1°3=81°5=3所形成的圖W………………… 40表目錄表2.1 6 階有洞的交換擬似群 …………………………………………10表2.2 6 階有洞的交換擬似群 …………………………………………12表2.3 8 階有洞的交換擬似群 …………………………………………13表2.4 5 階的擬似群({1,3,5,8,9},°)………………………14表2.5 10 階部分有洞的交換擬似群…………………………………15表2.6 10 階有洞的交換擬似群…………………………………………15
 [1] Alspach, B., Gavlas, H.: Cycle decompositions of Knand Kn−I, J. Comb. TheorySer. B 81(2001), 77–99.[2]Kirkman, T. P.: On a problem in combinations, Cambridge and Dublin Math.Journal 2 (1847), 191-204.[3] Lindner, C.C. and Rodger, C.A.: Design theory, Boca Raton, Florida, CRC Press(1997).[4] Šajna, M.: Cycle decompositions III: complete graphs and fixed length cycles. J.Comb. Des. 10(2002), 27–78.[5] Shyu, T. W.: Decomposition of complete graphs into cycles and stars, Graphsand Combinatorics (2011), pp. 1-13,doi:10.1007/s00373-011-1105-3.[6] Tarsi, M.: Decomposition of complete multigraph into stars. Discrete Math.26(1979), 273–278.[7] Yamamoto, S., Ikeda, H., Shige-ede, S., Ushio, K., Hamada, N.: On clawdecomposition of complete graphs and complete bipartie graphs. Hiroshima Math. J. 5(1975), 33–42.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 二倍圖的分割 2 均勻完全二部圖之多重充填與覆蓋 3 皇冠圖之多重分解 4 完全圖分割成5-太陽圖的探討 5 λ重完全圖分割成箏形圖 6 完全圖分割成4-迴圈或漢米爾頓迴圈之探討 7 邊著色圖中的混色子圖 8 完全圖分割成4-迴圈太陽圖之探討 9 完全三分圖分割成星狀圖的探討 10 圖形的L(3,2,1)標號 11 完全圖的路徑分割 12 完全雙分圖之星林分解數的探討 13 K2n,2n－C4n分割成長度為2k之迴圈的探討 14 完全二分圖K2m,2n分割成4、6、8、10迴圈之探討 15 圖形的線上即時點排序演算法

 無相關期刊

 1 4-迴圈裝填圖的探討 2 完全圖分割成5-太陽圖的探討 3 非負矩陣之非負平方根 4 基於簡易交通道路分層模型之車載最短路徑之研究 5 C4飽和圖的探討 6 高中數學排列組合單元教材內容分析 7 國中數學九年級教科書相似形之內容分析 8 利用區域切割之最短路徑規劃研究 9 不含K_2,3的二分極圖 10 不含 K_2,2 的二分極圖 11 車多項式 12 循環建構的2k-太陽圖設計 13 循環建構的p-太陽圖設計 14 簡約圖譜矩陣理論與其應用 15 具有最大無符號拉普拉斯譜半徑的圖及其相關主題之研究

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