| Abstract: | 完全圖Kn是一個具有n個點且其任兩點恰有一條邊相連的圖。一個圖G的分割是圖G的子圖所成的集合H = {H1,H2,…,Hk}使得E(Hi)∩E(Hj) = Ø (i ≠ j)且E(H1)∪E(H2)∪ … ∪E(Hk) = E(G)。若對於i = 1, 2, …, k，Hi均同構於H, 則稱G有一個H-分割或G可分割成圖H。假設H是一個圖，一個完全圖Kn的H-設計，記作(Kn,H)-設計，是一個序對(X,B)，其中X是Kn的點集合，B是Kn中與H同構的子圖所成的集合，而且Kn中任一條邊均會出現在B集中的唯一一個子圖裡。所以一個(Kn,H)-設計存在也就是Kn有一個H-分割。
一個牛型圖是指由一個三角形及在其中兩頂點各加上一條懸掛邊所成的圖。(Kn,B)-設計為一個牛型圖設計也就是Kn有一個B-分割, 其中B是一個牛型圖，亦即完全圖Kn可分割成牛型圖。
在第二章中，我們證明一個完全圖Kn分割成牛型圖的充分且必要條件為n ≡ 0, 1 (mod 5)。
在第三章中，討論完全圖Kn的最大裝填問題而得當n ≡ 2 or 4 (mod 5)時，最大裝填對應之遺留為一個邊所成的集合；當n ≡ 3 (mod 5)時，最大裝填對應之遺留為5種型態的三個邊所成的集合。由此，經適當的重排，我們獲得一個完全重邊圖λKn的牛型圖設計存在的充分且必要條件為λ≡ 0 (mod 5)或λ≢0 (mod 5)時n ≡ 0, 1 (mod 5)。
在第四章中，我們獲得在Kn中的兩個牛型圖設計其交集中相異的牛型圖個數集為Id(n)= {0, 1, 2,…, [n/5]}, 其中n >5，而Id(5)= {0}。若考慮其交集中相異的三角形的個數集則為IT(m) = {0, 1, 2,…, n(n−1)/10}。
最後，我們探討Doyen-Wilson問題，獲得完全圖Kn的牛型圖設計可嵌入完全圖Km的牛型圖設計之充分且必要條件為m ≥ 3n/2 + 1 或 m = n。
A complete graph Kn is a simple graph of order n whose vertices are pairwise adjacent. A decomposition of graph G is a collection H = {H1, H2, …, Hk} of subgraphs of G, such that E(Hi)∩E(Hj) = Ø (i ≠ j) and E(H1)∪E(H2)∪…∪E(Hk) = E(G). Furthermore, G has an H-decomposition or G can be decomposed into H, if Hi is isomorphic to H (1 ≤ i ≤ k). Let H be a graph, an H-design of a complete graph Kn, denoted by (Kn, H), is a pair (X, B), where X is the vertex set of the complete graph Kn and B is a collection of subgraphs of Kn, called blocks, such that each block is isomorphic to H, and any edge of Kn is contained in exactly one subgraph of Kn. Therefore, a (Kn, H)-design exists means Kn has an H-decomposition.
A bull is a graph B which is obtained by attaching two edges to two vertices of a triangle. A (Kn, B)-design is called a bull-design of order n .
In Chapter 2, we show that the necessary and sufficient condition of a bull-design of order n exist precisely when n ≡ 0, 1 (mod 5).
In Chapter 3, we consider the maximum packing of bull-design of order n. We obtain that the leave of maximum packing is a set of one edge if n ≡ 2 or 4 (mod 5) and a set of three edges if n ≡ 3 (mod 5). By the above results, we obtain that the necessary and sufficient conditions for the existence of bull-designs of a complete multi-partite graph λKn are the follows: λ ≡ 0 (mod 5) or λ≢0 (mod 5) and n ≡ 0, 1 (mod 5).
In Chapter 4, we obtain that the spectrum of bull-design of order n intersecting in pairwise disjoint blocks is 0, 1, 2,…, [n/5], when n>5 and n ≡ 0, 1 (mod 5), and the spectrum of bull-design of order 5 intersecting in pairwise disjoint blocks is 0. We also show that the spectrum of triangle intersection numbers of two bull-design of order n is 0, 1, 2,…, n(n−1)/10, for n ≡ 0, 1 (mod 5).
In Chapter 5, we obtain that a bull-design of order n can be embedded in a bull-design of order m if and only if m ≥ 3n/2 + 1 or m = n. This produces a generalization of the Doyen–Wilson theorem for bull-designs. |
