淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0901201219574800
中文論文名稱 循環建構的p-太陽圖設計
英文論文名稱 Cyclically Constructed p-sun Graph Designs
校院名稱 淡江大學
系所名稱(中) 數學學系博士班
系所名稱(英) Department of Mathematics
學年度 100
學期 1
出版年 101
研究生中文姓名 林遠隆
研究生英文姓名 Yuan-Lung Lin
學號 894150019
學位類別 博士
語文別 英文
口試日期 2011-12-15
論文頁數 77頁
口試委員 指導教授-高金美
委員-傅恆霖
委員-胡守仁
委員-譚必信
委員-周兆智
委員-顏經和
委員-潘志實
中文關鍵字 史坦那三元系  分割  循環  3 -太陽圖  3 -太陽圖系統 
英文關鍵字 Steiner triple system  k-sun graph  k-sun system  decomposition  cyclic 
學科別分類
中文摘要 一個完全多邊圖λK_n 是一個n個點的圖,其中任意兩個相異點皆有λ條邊相連。一個圖G的分割是圖G的子圖所成的集合H = {H_1, H_2, ..., H_t},使得E(H_1)∪E(H_2)∪...∪E(H_t) = E(G)而且E(H_i)∩E(H_j) = φ,其中i ≠ j。若對於i = 1, 2, ..., t,H_i 皆同構於H,則我們說G有一個H–分割。
一個k-太陽圖S(C_k) 可以由一個k–迴圈在每個點上加上一條懸掛邊得到。 一個λ–重邊圖λK_v的G–設計,記作(K_v,G,λ)–設計,是一個序對(X,B),其中X是K_v 的點集合,B是K_v中與G同構子圖所成的集合,而且任意一條K_v 中的邊皆會出現在B 集合中的λ個子圖裡。若λ=1,則我們將此設計簡稱為(K_v,G)–設計。一個(K_v, S(C_k), λ) –設計是將一個完全多邊圖λK_v分割成k -太陽圖。
在第二章中,我們得到了將一個至少有兩個部分點集合大小一樣的完全三分圖分割成S(C_3)的充分且必要條件。更進一步地,對於正整數n,我們將K_{2n,2n,2n} 循環地分割成3 -太陽圖。此外,我們將一個n個點的循環史坦那三元系嵌入至一個大小為2n - 1的3 -太陽圖系統中,其中n ≡ 1 (mod 6)。
在第三章中,我們利用K_{p,p,r}分割成3 -太陽圖的結果,遞迴地建構了一個(K_v, S(C_3)) –設計。在3.2節中,當v ≡ 1(mod 12)時,我們分別得到了循環(K_v, S(C_3)) –設計。當v ≡ 0, 4 (mod 12)時,1 –旋轉(K_v, S(C_3)) –設計。當v ≡ 9 (mod 12)時,我們循環建構一個(K_v, S(C_3))。更進一步地,在3.3節中,當λn(n - 1) ≡ 0 (mod 12)時,對於所有的正整數λ,我們循環建構了(K_v, S(C_3), λ) –設計。
在第四章中,我們考慮了(K_v, S(C_5)) –設計的建構法。當v ≡ 1, 5 (mod 20)時,我們得到了一個循環(K_v, S(C_5)) –設計。當v ≡ 0 (mod 20)時,我們得到了一個1 –旋轉(K_v, S(C_5)) –設計。對於v ≡ 16 (mod 20)的情況,我們利用循環式的建構法建構了一個(K_v, S(C_5)) –設計。
英文摘要 A complete multigraph of order n and index λ, denoted by λKn, is a graph with n vertices, where any two distinct vertices u and v are joined by λ edges uv. A decomposition of a graph G is a collection H = {H_1, H_2, ..., H_t} of subgraphs of G such that E(H_1)∪E(H_2)∪...∪E(H_t) = E(G) and E(H_i)∩E(H_j) = φ for i ≠ j. If H_i is isomorphic to a graph H for each i = 1, 2, ..., t, then we say that G has an H-decomposition. A k-sun graph S(C_k) is a graph obtained from a k-cycle by adding a pendent edge to each vertex of the k-cycle. Let G be a graph. A G-design of λK_v, denoted by (K_v, G, λ)-design, is a pair of (X, B) where X is the vertex set of K_v and B is a collection of subgraphs of K_v, called blocks, such that each block is isomorphic to G and any edge in K_v is in exactly λ blocks of B. If λ = 1, then we call it a (K_v, G)-design for short. A (K_v, S(C_k), λ)-design is a decomposition of the complete multigraph λKv into k-sun graphs.
In Chapter 2, we obtain the necessary and sufficient conditions for the decomposition of complete tripartite graphs with at least two partite sets having the same size into 3-suns and give the constructions to decompose K_{p,p,r} into 3-suns. Moreover, we decompose K_{2n,2n,2n} into 3-suns cyclically, and embed a cyclic Steiner triple system of order n into a 3-sun system of order 2n - 1, for n ≡ 1 (mod 6).
In Chapter 3, we use the result of decomposing Kp,p,r into 3-suns to construct a (K_v, S(C_3))-design recursively. In Section 3.2, we obtain the cyclic (K_v, S(C_3))-design for v ≡ 1(mod 12), the 1-rotational (K_v, S(C_3))-design for v ≡ 0, 4 (mod 12), and then cyclically construct (K_v, S(C_3))-design for v ≡ 9 (mod 12). Furthermore, in Section 3.3, we cyclically construct (K_v, S(C_3), λ)-design for all λ when λn(n - 1) ≡ 0 (mod 12).
In Chapter 4, we consider the construction of (K_v, S(C_5))-designs. We obtain a cyclic 5-sun system of order v as v ≡ 1, 5 (mod 20) and a 1-rotational 5-sun system of order v as v ≡ 0 (mod 20). For v ≡ 16 (mod 20), we use recursive construction to get (K_v, S(C_5))-design.
論文目次 1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Definitions and Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Graph Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Cyclic and 1-rotational system . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Background of Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Decompose Kp;q;r into 3-suns 10
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Decomposing Kp;p;r into 3-suns . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Decomposing K2n;2n;2n into cyclic 3-suns . . . . . . . . . . . . . . . . . . . 14
2.4 Embedding a cyclic Steiner triple system into a 3-sun system . . . . . . . . 16
3 On the Existence of 3-sun System 18
3.1 3-sun system of order n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Cyclic 3-sun system of order n . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.1 Definitions and Preliminaries . . . . . . . . . . . . . . . . . . . . . 23
3.2.2 Cyclic 3-sun system of order n . . . . . . . . . . . . . . . . . . . . . 31
3.3 Cyclic (Kn,S(C3),λ)-design . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4 5-sun System 54
4.1 Preliminary and Small Cases . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2 Recursive Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3 Cyclic 5-sun system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5 Conclusion and Open Questions 68
References 70
Appendix 75
參考文獻 [1] B. Alspach, Research problems, problem 3, Discrete Math., 36:333, 1981.
[2]B. Alspach, ”The wonderful Walecki construction”, 2006, April [Lecture notes].
[3] B. Alspach and H. Gavlas, Cycle decompositions of Kn and Kn−I, J. Combin. Theory Ser. B, 81(1):77–99 , 2001.
[4] I. Anderson, Combinatorial designs: construction methods, Ellis Horwood Limited, 1990.
[5] I. Anderson, Combinatorial Designs and Tournaments, Charendom Press, Oxford(2006).
[6] R. Anitha and R. S. Lekshmi, N-Sun Decomposition of Complete Graphs and Complete Bipartite Graphs, World Academy of Science, Engineering and Technology, 27, 262–266, 2007.
[7] R. Anitha and R. S. Lekshmi, N-Sun Decomposition of Complete, Complete Bipartite and Some Harary Graphs, International Journal of Computational and Mathematical
Sciences, 1, 33-38, 2008.
[8] P. N. Balister, On Alspach conjecture, Combin. Probab. Comput., 10(2):95–125, 2001.
[9] J.-C. Bermond, and D. Coudert, Traffic grooming in unidirectional WDM ring networks using design theory, in Proceedings of the IEEE ICC, Anchorage, AK, 2003, pp. 1402–1406.
[10] D. Bryant, Cycle decompositions of complete graphs, Survey in combinatorics 2007, volume 346 of Londan Math. Soc. Lecture Note Ser., pages 67–97. Cambridge Univ. Press, Cambridge, 2007.
[11] D. Bryant and C. A. Rodger, Cycle decompositions, The CRC Handbook of Combinatorial Designs, 2nd edition (Eds. C. J. Colbourn, J. H. Dinitz), pages 373–382. CRC Press, Boca Raton, 2007.
[12] D. Bryant and D. Horsley, Packing cycles in complete graphs, J. Combin. Theory Ser. B, 98(5):1014–1037, 2008.
[13] M. Buratti, Rotational k-cycle systems of order v < 3k; another proof of the existence of odd cycle systems, J. Combin. Des., 11(6):433–441, 2003.
[14] M. Buratti, Existence of 1-Rotational k-Cycle Systems of the Complete Graph, Graph Comb., 20(1):41–46, 2004.
[15] M. Buratti and A.Del Fra, Existence of cyclic k-cycle systems of the complete graph, Discrete Math., 261(1-3):113–125, 2003.
[16] Zheng-Zhi Cheng, The study of 3-sun decomposition of 2-fold complete graphs, Master thesis, Tamkang University, Taiwan, 2010.
[17] C.J. Colbourn and A. Rosa, Triple Systems, Charendom Press, Oxford(1999).
[18] C.J. Colbourn and Jeffrey H. Dinitz, Handbook of Combinatorial Designs, 2nd. Ed. (Discrete Mathematics and Its Applications), Chapman & Hall/CRC, 2006.
[19] R.O. Davies, On Langford’s problem, Math. Gazette, 43:253–255, 1959.
[20] H.-L. Fu and S.-L. Wu, Cyclically decomposing the complete graph into cycles, Discrete Math., 282(1-3):267-273, 2004.
[21] Chin-Mei Fu, Nan-Hua Jhuang, Yuan-Lung Lin and Hsiao-Ming Sung, From Steiner triple systems to 3-sun systems, Taiwanese-J-Math, 2012.
[22] L. Heffter, ‥U ber Nachbarconfigurationen, Tripelsysteme und metacyklische Gruppen, Deutsche Mathem. Vereining. Jahresber., 5, 67–69, 1896.
[23] A. J. W. Hilton, On Steiner and similar triple systems, Math. Scand., 24:208–216, 1969.
[24] F. K. Hwang, An isomorphic factorization of the complete graph, J. Graph Theory, 19 (1995), pp. 333–337.
[25] T. P. Kirkman, On a problem in combinations, Cambridge and Dublin Math. Journal, 2 (1847), 191–204.
[26] T. P. Kirkman, Query VI., Lady’s and Gentleman’s Diary, (1850), 48.
[27] Z. Liang and J. Guo, Decomposition of complete multigraphs into crown graphs, J. Appl. Math. & Computing, Vol. 32, 507–517, 2010.
[28] 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.
[29] C. C. Lindner and C. A. Rodger, Design Theory, CRC Press, 1997.
[30] C.C. Lindner, G. Quattrochi, C.A. Rodger, Embedding Steiner triple systems in hexagon triple systems, Discrete Math., 2008.
[31] M. Mishima and H. Fu, Resolvable even-cycle systems with a 1-rotational automorphism, J. Combin. Des., 11:394–407, 2003.
[32] E. Netto, Zur Theorie der Tripelsysteme, Math. Ann., 42:143–152, 1893.
[33] E.S. O’Keefe, Verification of a conjecture of T. Skolem, Math. Scand., 9:80–82, 1961.
[34] R. Peltesohn, Eine L‥osung der beiden Heffterschen Differenzenprobleme, Compositio Math., 6, 251–257, 1939.
[35] A. Rosa, Poznamka o cyklickych Steinerovych systemoch trojic, Math. Fyz. Cas., 16:285–290, 1966.
[36] M. Sajna, Cycle decompositions of Kn and Kn − I, PhD thesis, Simon Fraser University, Canada, 1999.
[37] M. Sajna, Cycle decompositions III. Complete graphs and fixed length cycles, J. Combin. Des., 10(1):27–78, 2002.
[38] T. Skolem, On certain distributions of integers in pairs with given differences, Math. Scand., 5:57–68, 1957.
[39] T. Skolem, Some remarks on the triple systems of Steiner, Math. Scand., 6:273–280, 1958.
[40] W.D. Wallis, Combinatorial Design, Marcel Dekker, New York and Besel (1988).
[41] S.-L. Wu and H.-L. Fu, Cyclic m-cycle systems with m ≤ 32 or m = 2q with q a prime power, J. Combin. Des., 14:66–81, 2006.
[42] S.-L. Wu and H.-C. Lu, Cyclically Decomposing the Complete Graph into Cycles with Pendent Edges, Ars Comb., 86, 2008.
[43] W. S. B. Woolhouse, Prize question 1733, Lady’s and Gentleman’s Diary, (1844).
[44] Jian-Xing Yin and Bu-Sheng Gong, G-designs with |V (G)| = 6, Combinatorial designs and applications (Huangshan, 1988), 201–218. CRC Press, Lecture Notes in Pure
and Appl. Math., 126, Dekker, New York, 1990.
[45] Rucong Zhang, Gennian Ge, Alan C. H. Ling, Hung-Lin Fu, adn Yukiyasu Mutoh, The existence of r × 4 grid-block designs with r = 3; 4, Discrete Math., Vol. 23, No. 2, pp. 1045–1062, 2009.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-01-11公開。
  • 同意授權瀏覽/列印電子全文服務,於2012-01-11起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信