Cyclically constructed p-sun graph designs

機構典藏 > College of Sciences > Graduate Institute & Department of Mathematics > Thesis > Item 987654321/77377

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/77377

Title:	Cyclically constructed p-sun graph designs
Other Titles:	循環建構的p-太陽圖設計
Authors:	林遠隆;Lin, Yuan-Lung
Contributors:	淡江大學數學學系博士班高金美;Fu, Chin-Mei Kau
Keywords:	史坦那三元系;分割;循環;3 -太陽圖;3 -太陽圖系統;Steiner triple system;k-sun graph;k-sun system;decomposition;cyclic
Date:	2012
Issue Date:	2012-06-21 06:38:13 (UTC+8)
Abstract:	一個完全多邊圖λ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.
Appears in Collections:	[Graduate Institute & Department of Mathematics] Thesis

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	411	View/Open

Loading...