圖---設計的研究(I)

Abstract

令G為一圖，如果圖G的邊集合E(G)可以分割成一些子集合，使得每一個子集合 所導出的子圖都與圖H同構，則稱G有一個H-分割或H-設計,通常以H|G表示。由於 一個平衡不完全區組設計(BIBD)，2-(,,vkλ)設計的存在性對應於|vkKKλ是否成立的 研究，所以圖-設計的研究不但可以處理BIBD的建構問題，隨著G與H的選擇更可以 推廣至更一般化的組合設計之研究。例如，當G為時，建構出來的就是可分組 ()mnKλ 設計(GDD)，而當H為圈(Cycle)時，可得到圈系等等。 在這個研究計畫中，我們除了繼續探討傳統的BIBD與GDD的存在性，我們將研 究以下幾個問題： (1) 令H為，，G為kC3k?() G m δ?的n點圖。當 ()mfn=時，何種f能使得 H|G ? (Nash-Williams猜測當3k=時()3/4fnn=. (1970)) (2) 令H為，，為kC3k?'GnK的子圖。何種能使得'G|'nHKG?？ (3) 探討H不為的情況，例如kCrHKKc =×，在DNA Library Screening |rc n KKK×的探 討扮演著非常重要的角色。 (4) 除了一般的分割之外，探討循環分割(Cyclic Decomposition)以及旋轉分割 (k-Rotational)的可行性。