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

朱 莉

（南通職業大學 數學教研室，江蘇 南通 226007）

1 問題提出

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

2 預備知識

3-一致超圖的圖分解可看作組合設計中3-設計的推廣。3-設計（記為t-（v，K，λ）），是一個關聯結構（V，B），滿足條件：（1）V 是v 元點集；（2）B是V 的子集族（B 中的元素稱為設計的區組），且每一個區組b∈B 有∈K；（3）V 中的任意一個3-元子集恰好出現在λ 個區組中。3-設計的相關內容可參見文獻[9-10]。下列兩個結論分別來自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 的條件可有兩種情形：當λ≡1（mod 2）時，v≡0，1，2（mod 4）；當λ≡0（mod 2）時，v≥4。

3 定理1 的證明

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

（2）λ=2，v≥4。

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