系統識別號 | U0002-0507201214180300 |
---|---|
DOI | 10.6846/TKU.2012.00196 |
論文名稱(中文) | 循環建構的2k-太陽圖設計 |
論文名稱(英文) | Cyclically Constructed 2k-sun Graph Designs |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 數學學系博士班 |
系所名稱(英文) | Department of Mathematics |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 100 |
學期 | 2 |
出版年 | 101 |
研究生(中文) | 宋曉明 |
研究生(英文) | Hsiao-Ming Sung |
學號 | 893150069 |
學位類別 | 博士 |
語言別 | 英文 |
第二語言別 | |
口試日期 | 2012-06-15 |
論文頁數 | 61頁 |
口試委員 |
指導教授
-
高金美
委員 - 高金美 委員 - 傅恆霖 委員 - 林強 委員 - 黃文中 委員 - 周兆智 委員 - 胡守仁 委員 - 潘志實 |
關鍵字(中) |
圖形分割 k-太陽圖 k-太陽圖系統 循環 1-旋轉 完全圖 完全均分圖 |
關鍵字(英) |
Graph decomposition k-sun graph k-sun system cyclic 1-rotational complete graph complete equipartite graph |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
<pre> 一個含有 v 個點的完全圖 Kv是指含有 v 個點且任二點都有邊相連的圖,又 稱為 v 階完全圖。 一個圖頂點集合為 V 可以分成兩個互斥的集合 V1 與 V2,且 V1中的每一點都與 V2中的每一點有邊相連,則稱此圖為一個完全二 分圖。一個圖的頂點集合 V 可以分成 m 個兩兩互斥的集合 V1,V2,··· ,Vm, 當 i neq j 時, Vi 中的每一點都與 Vj 中的每一點有邊相連,則稱此圖為完全 m 分圖。 當 V1,V2,··· ,Vm 中元素的個數都為 n 時,則稱此圖為完全均分圖 Km(n)。 一個 k-太陽圖 S(Ck) 是將一個 k-迴圈上的每一點分別向外連接一個 懸掛邊,即另一端點度數為 1 的點,所成的圖。 一個圖 G 的分割是圖 G 的子圖 H1,H2,··· ,Ht 所成的集合 H,其中 E(H1)∪E(H2)∪···∪E(Ht) = E(G) 且 對於所有 i 6= j,E(Hi)∩E(Hj) = emptyset。若對於每一個 i = 1,2,··· ,t, Hi皆同構於 H,則我們說 G 有一個 H-分割。一個 v 階的 k-太陽圖系統是指由 v 階的完全圖 Kv分割成 k-太陽圖後, 這些 k- 太陽圖所成的集合。 存在 v 階 k-太陽圖系統的 v 所成的集合,稱為 k-太陽圖系統的譜 Spec(k) 。 本論文主要包括二個部份,一個是在完全圖中建構 k-太陽圖系統, 另一個 是證明在完全均分圖中有 k-太陽圖-分割。 在第三章中,當k = 6,10,14,2t(t geq 2)時,我們得到了k-太陽圖系統的譜 如下: (1) Spec(2t) = {v|v ≡ 0,1 (mod 2t+2)} 其中 t geq 2. (2) Spec(6) = {v|v ≡ 0,1,9,16 (mod 24)}. (3) Spec(10) = {v|v ≡ 0,1,16,25 (mod 40)}. (4) Spec(14) = {v|v ≡ 0,1,8,49 (mod 56)}. 並且對於階數大於 4k 時,我們建構出奇數階的循環 k-太陽圖系統與偶數階 的1-旋轉 k-太陽圖系統。 在第四章中,我們將焦點放在完全均分圖是否有 k-太陽圖-分割。當 k 為偶數且 n ≡ 0 (mod 2k) 時,我們證明一個完全二分圖 Kn,n 有 2k-太陽 圖-分割;而當(m,n) 滿足 mn geq 8 且 m(m - 1)n^2≡ 0 (mod 16)時, 除了 (m,n) = (4,2) 之外,我們則證明了完全均分圖 Km(n)有 4-太陽圖-分割。 </pre> |
英文摘要 |
<pre> A complete graph with v vertices, denoted by Kv, is a simple graph whose vertices are mutually adjacent. A complete bipartite graph is a graph G = (V,E) where V can be divided into two disjoint sets V1 and V2 and E contains all edges connecting every vertex in V1with all vertices in V2. If |V1| = m and |V2| = n, then G can be denoted as Km,n. A complete m-partite graph G = (V,E) is a graph such that the vertex set V can be partitioned into m parts, V1,V2,··· ,Vm, and E contains all edges which connect all vertices belong to different parts. If |Vi| = nifor each i = 1,2,··· ,m, then G can be denoted as Kn1,n2,···,nm. If n1= n2= ··· = nm= n, this graph is called a complete equipartite graph with m parts of size n, and denoted by Km(n). A k-sun graph S(Ck) is obtained from the cycle of length k, Ck, by adding a pendant edge to each vertex of Ck. A decomposition of a graph G is a collection H = {H1,H2,··· ,Ht} of subgraphs of G such that E(H1) ∪ E(H2) ∪ ··· ∪ E(Ht) = E(G) and E(Hi)∩E(Hj) = emptyset for each i neq j. If Hi is isomorphic to a subgraph H of G for each i = 1,2,··· ,t, then we say that G has an H-decomposition. A k-sun system of order v is a decomposition of the complete graph Kv into k-sun graphs. The set of values of v for which there exists a k-sun system of order v is called the spectrum of a k-sun system, denoted by Spec(k). This dissertation includes two parts. One is about constructing a k-sun system of order v and another is about proving that complete equipartite graphs have k-sun decompositions. In chapter 3, when k = 6,10,14, and 2tfor t geq 2, we obtain the spectrum of k-sun systems as follows. (1) Spec(2t) = {v|v ≡ 0,1 (mod 2t+2)} for t geq 2, (2) Spec(6) = {v|v ≡ 0,1,9,16 (mod 24)}, (3) Spec(10) = {v|v ≡ 0,1,16,25 (mod 40)}, and (4) Spec(14) = {v|v ≡ 0,1,8,49 (mod 56)}. We give the construction of cyclic k-sun system of odd order and 1-rotational k-sun system of even order when the order is greater than 4k. In chapter 4, we give the construction of 2k-sun decomposition of Kn,nas k is even and n ≡ 0 (mod 2k) and construct 4-sun decomposition of Km(n)for mn geq 8 and m(m - 1)n^2≡ 0 (mod 16) except (m,n) = (4,2). </pre> |
第三語言摘要 | |
論文目次 |
<pre> Contents 1 Introduction 1 2 Preliminaries 5 2.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Block Designs . . . . . . . . . . . . . . . . . . . . . . . . . . .8 2.3 Graph Decompositions . . . . . . . . . . . . . . . . . . . . . . . 10 3 2k-sun system of order v 14 3.1 The Spectrum . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 2k-sun system . . . . . . . . . . . . . . . . . . . . . . . . . . .17 3.3 6-sun system . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4 10-sun system . . . . . . . . . . . . . . . . . . . . . . . . . . .26 3.5 14-sun system . . . . . . . . . . . . . . . . . . . . . . . . . . .31 4 Decomposing complete equipartite graph into 2k-sun graphs 39 4.1 Decomposing Kn,n into 2k-sun graphs . . . . . . . . . . . . . . . .39 4.2 Decomposing Km(n) into 4-sun graphs . . . . . . . . . . . . . . . .42 5 Concluding Remarks 56 References 57 List of Figures 2.1 A graph G and 3G . . . . . . . . . . . . . . . . . . . . . . . .. . .6 2.2 Path and star. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 K5, K2,2, and K4(2). . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 4-sun graph S(C4). . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5 {H1,H2} is a decomposition of G. . . . . . . . . . . . . . . . . . . 11 2.6 A C3-decomposition of K7. . . . . . . . . . . . . . . . . . . . . . .11 3.1 A S(C4) with the difference set {±1,±1,±1,±1,±3,±5,±5,±5}. . . . . . 15 3.2 A S(C10) with the difference set {±1(5),±2(5),±3(5),±12(5)}. . . . . 16 3.3 A base block of 4-sun system of order 16. . . . . . . . . . . . . . .19 3.4 A base block of 8-sun system of order 32. . . . . . . . . . . . . . .21 3.5 Two base blocks of 6-sun system of order 33. . . . . . . . . . . . . 23 3.6 Two blocks of 6-sun system of order 16. . . . . . . . . . . . . . . .24 3.7 Three base blocks of 6-sun system of order 40. . . . . . . . . . . . 25 3.8 Three base blocks of 10-sun system of order 25. . . . . . . . . . . .27 3.9 Four base blocks of 10-sun system of order 65. . . . . . . . . . . . 29 3.10 Three base blocks of 10-sun system of order 56. . . . . . . . . . . 31 3.11 Six base blocks of 14-sun system of order 49. . . . . . . . . . . . 32 3.12 Seven base blocks of 14-sun system of order 105. . . . . . . . . . .34 3.13 Two base blocks of 14-sun system of order 64. . . . . . . . . . . . 37 4.1 G and G(2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40 4.2 A decomposition of C4(2) into two S(C4). . . . . . . . . . . . . . . 41 4.3 A decomposition of C6(2)into three 4-sun graphs. . . . . . . . . . . 45 4.4 A decomposition of (G1∪ G2)(2)into 5 4-sun graphs. . . . . . . . . .46 4.5 The 3-regular graph H12. . . . . . . . . . . . . . . . . . . . . . . 48 4.6 The 3-regular graph F8. . . . . . . . . . . . . . . . . . . . . . . .49 4.7 The 3-regular graph F12. . . . . . . . . . . . . . . . . . . . . . . 49 4.8 A decomposition of K4(3) into two 12-cycles, two 6-cycles, and a H12. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 </pre> |
參考文獻 |
<pre> [1] A. D. Akinola, Decomposition of Cr[Km] into sunlet graphs, IJSER., Vol. 2, Issue 10, 2011. [2] B. Alspach, Research problems, Problem 3, Discrete Math.36(1981), 333. [3] B. Alspach and H. Gavlas, Cycle decomposition of Kn and Kn - I, J. Comb. Theory Ser. B, Academic Press, Inc., 2001, Vol. 81(1), pp. 77-99. [4] B. Alspach, The wonderful Walecki construction, Bull. Inst. Combin. Appl. 52 (2008), 7–20. [5] R. Anitha and R. S. Lekshmi, N-sun decomposition of domplete graphs and complete bipartite graphs, World Acad. Sci., Eng. and Tech., 2007, Vol. 27, pp. 262-266. [6] R. Anitha and R. S. Lekshmi, N-Sun Decomposition of Complete, Complete Bipartite and Some Harary Graphs, Int. J. Math. Sci., 2008, Vol. 2, pp. 33-38. [7] J. C. Bermond and J. Sch‥onheim, G-decomposition of Kn, where G has four vertices or less, Discrete Math., 1977, Vol. 19(2), pp. 113-120. [8] J. C. Bermond, C. Huang, A. Rosa, and D. Sotteau, Decomposition of complete graphs into isomorphic subgraphs with ?ve vertices, Ars Combin., 1980, Vol. 10, pp. 211-254. [9] D. Bryant, Cycle decompositions of complete graphs, in Surveys in Combinatorics 2007, Cambridge University Press, 2007, pp. 67–97. [10] M. Buratti, A description of any regular or 1-rotational design by difference methods, Booklet of the Abstracts of Combinatorics, 2000. http://www.mat.uniroma1.it/~combinat/gaeta/Combinatorics2000.pdf. [11] M. Buratti, Existence of 1-Rotational k-cycle systems of the complete graph, graph. Comb., 2004, Vol. 20(1), pp. 41-46. [12] M. Buratti, Rotational k-cycle systems of order v < 3k; another proof of the existence of odd cycle systems, J. Combin. Des., 2003, Vol. 11(6),pp. 433-441. [13] M. Buratti and A. D. Fra, Existence of cyclic k-cycle systems of the complete graph, Discrete Math., 2003, Vol. 261(1-3), pp. 113-125. [14] C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, 2nd. Ed. (Discrete Mathematics and Its Applications) Chapman & Hall/CRC, 2006. [15] R. Frucht, Graceful numbering of wheels and related graphs, Ann. N.Y. Acad. Sci., 1979, Vol. 319, pp. 219-229. [16] C.- M. Fu, N.- H. Jhuang, Y.- L. Lin and H.- M. Sung, From Steiner triple systems to 3-sun systems, Taiwanese-J-Math., Vol. 16, NO. 2, pp. 531-543, 2012. [17] H. -L. Fu and S. -L. Wu, Cyclically decomposing the complete graph into cycles, Discrete Math., 2004, Vol. 282(1-3), pp. 267-273. [18] T. Grace,On sequential labellings of graphs, J. Graph Theory, 1983, Vol 7, pp. 195-201. [19] F. Harary, Graph Theory. Addison-Wesley, New York, 1969. [20] Z. Liang and J. Guo, Decomposition of complete multigraphs into crown graphs, J. Appl. Math. & Computing, Vol. 32, 507-517, 2010. [21] Z. Liang, J. Guo, and J. Wang, On the crown graph decompositions containing odd cycle, International Journal of Combinatorial Graph Theory and Applications, 2, 125-160, 2008. [22] Y.- L. Lin, Cyclically constructed p-sun graph designs, Ph.D. dissertation, Tamkang University, R.O.C, 2012. [23] M. Mishima and H.-L. Fu, Resolvable even-cycle systems with a 1-rotational automorphism, J. Combin. Des., 2003, Vol. 11, pp. 394-407. [24] M. Sajna, Cycle decompositions III : Cycle decompositions III: complete graphs and fixed length cycles, J. Combin. Des., 2002, Vol. 10, pp. 27-78. [25] D. Sotteau, Decomposition of Km,n(K*m,n) into cycles (circuits) of length 2k., J. Combin. Theory Ser. B, 1981, Vol. 30, pp. 75-81. [26] M. Tarsi, Decomposition of a complete multigraph into simple paths, J Comb. Theory Ser A, 1983, Vol. 34, pp. 60-70. [27] M. Tarsi, Decomposition of complete multigraphs into stars, Discret Math., 1979, Vol. 26, pp. 273-278. [28] D. B. West, Introduction to Graph Theory (2nd Edition), Prentice Hal August 2000. [29] S. -L. Wu and H. -L. Fu, Cyclic m-cycle systems with m ? 32 or m = 2 with q a prime power, J. Combin. Des., 2006, Vol. 14, pp. 66-81 [30] S. -L. Wu and H. -C. Lu, Cyclically decomposing the complete grap into cycles with pendent edges, Ars Comb., 2008, Vol. 86. [31] J. Yin and B. Gong, Existence of G-designs with |V (G)| = 6, Combinatiorial Designs and Applications. Lect. Notes in Pure and Applied Math 1990, Vol. 126, pp. 201-218. CRC Press, Boca Raton. [32] 沈灝, 組合設計理論(第二版), 上海交通大學出版社, 2008 年1月. </pre> |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信