3-一致完全超圖的-分解

朱 莉

（南通職業(yè)大學(xué) 數(shù)學(xué)教研室，江蘇 南通 226007）

1 問(wèn)題提出

超圖是有限集合的子集系統(tǒng)，是離散數(shù)學(xué)中的最一般結(jié)構(gòu)。超圖H 定義為一個(gè)有序二元組H=（X，E），其中：X 是一個(gè)有限非空集合，其元素稱為超圖H 的頂點(diǎn)；E 是X 的一組非空子集簇，其元素是X 的一個(gè)非空子集，被稱為邊或超邊。如果超圖H 的每一條邊都恰好包含k 個(gè)頂點(diǎn)，則稱它是k-一致的。2-一致超圖就是傳統(tǒng)意義上的圖。關(guān)于超圖的相關(guān)概念和理論，可參閱文獻(xiàn)[1-2]。

2 預(yù)備知識(shí)

3-一致超圖的圖分解可看作組合設(shè)計(jì)中3-設(shè)計(jì)的推廣。3-設(shè)計(jì)（記為t-（v，K，λ）），是一個(gè)關(guān)聯(lián)結(jié)構(gòu)（V，B），滿足條件：（1）V 是v 元點(diǎn)集；（2）B是V 的子集族（B 中的元素稱為設(shè)計(jì)的區(qū)組），且每一個(gè)區(qū)組b∈B 有∈K；（3）V 中的任意一個(gè)3-元子集恰好出現(xiàn)在λ 個(gè)區(qū)組中。3-設(shè)計(jì)的相關(guān)內(nèi)容可參見(jiàn)文獻(xiàn)[9-10]。下列兩個(gè)結(jié)論分別來(lái)自Hanani[11]和Ji[12]。

定理23-（v，{k：4≤k≤34}，1）存在的充分必要條件是v≥4。

定理33-（v，{4，5，6}，1）存在的充分必要條件是v≡0，1，2（mod 4）且v≥4，v≠9，13。

將λ 劃分為λ≡1（mod 2）和λ≡0（mod 2），則引理1 的條件可有兩種情形：當(dāng)λ≡1（mod 2）時(shí)，v≡0，1，2（mod 4）；當(dāng)λ≡0（mod 2）時(shí)，v≥4。

3 定理1 的證明

（1）λ=1，v≡0，1，2（mod 4）；

（2）λ=2，v≥4。

結(jié)合引理4，引理5 和引理1，完成了定理1的證明。