推廣的幾乎可分解的26圈系

蒲利群，方佳，馬俊

（1.鄭州大學 數學系，河南 鄭州450001；2.上海交通大學 數學系，上海200240）

1 基本知識

（X，C）稱為階是n的k圈系，如果C為邊不交的k圈集合，且為完全無向圖Kn邊集的劃分［1-8］，其中Kn的頂點集為X，｜X｜＝n.

圈系（X，C）稱為可分解圈系，如果C中的圈能夠分為若干個集合，每個集合中的元素為邊不交的圈，其為完全圖Kn的一個2-正則支撐子圖，稱該集合為一個平行類.

下面給出完全圖Kn的可分解圈系譜的存在性定理.

定理1［2］階為n的可分解的k圈系存在的充分必要條件：n≥k≥3，n和k是奇數，并且k整除n.

圈系（X，C）稱為幾乎可分解圈系（almost resolvability cycle system，ARCS）；如果C中k圈能夠盡可能多地劃分為幾乎平行類，并且剩余的k圈頂點互不相交，用kARCS（n）表示.3ARCS（n）［9］和6ARCS（n）［5］已經得到解決.

2 三個基本構造

給出的3個例子是構造26GARCS（n）的基礎.其中：V（G）表示圖G的點集；Kn表示階為n的完全圖；Km，n表示兩個部分的點集數分別為m和n的完全二部圖.

例1 26GARCS（65）

令點集V（K65）＝｛ij｜i∈Z13，j＝1，2，3，4，5，有40個幾乎平行類.13個幾乎平行類是在模13下循環，其下標被固定為

令點集V（K65／K13）＝｛ij｜i∈Z13，j＝1，2，3，4，5｝，點集H＝｛i1｜i∈Z13｝，其中：H為階 13的洞，并且H?V（K65／K13）.如果K65／K13的邊集能夠劃分成26圈系，稱這個圈系為階65，洞13的26圈系.

集合F1含下面的兩個幾乎平行類，該平行類在模13下循環，其下標固定為

其中：F1中k圈與洞H中的點相交，但是F2∪S中所有的26圈與洞H中的點不相交.

例3 26GARCS（117）

令V（K117）＝｛ij｜i∈Z13，j＝1，2，3，…，9｝｝.該圈系含有65個幾乎平行類和一個短平行類，其中每一類包含4個26圈.

兩個幾乎平行類在模13下循環，其下標是固定的，即

以上26個幾乎平行類使用了所有的純差和部分的混差，剩余的混差下標，如表1所示.因下標相同的兩個混差可構造一個26圈，表1由包含4對下標的列和包含一對下標列組成.

表1 剩余混差的下標Tab.1 Remaining mixed difference subscript

使用相同的方法可構造其他所有的幾乎平行類.

2 構造26GARCS（n）s

為了證明主要的結果，需要定理2.

定理2［7］二部圖K2m，2m能劃分成2k圈的平行類的充分必要條件是2k｜2m，但圖K6，6不能劃分成6圈的平行類.

下面給出26GARCS（52t＋13）的構造，其中：2t≥6.

Ⅲ）現在已經窮盡了3）中的所有26圈，剩余的圈集有1）中的14個幾乎平行類，F2中12個幾乎平行類和對每一個hi，2≤i≤t的S中的短平行類.由于F2中的幾乎平行類與洞∞中的點不相交，將1）中12個幾乎平行類與每一個洞hi，i≥2，F2中的12個幾乎平行類配對.則得到C中的12個幾乎平行類.

Ⅳ）目前剩余的是1）中的兩個幾乎平行類和每一個洞hi，i≥2中的短平行類.將1）中的一個幾乎平行類與每一個洞hi，i≥2中的短平行類配對.則得到C中的一個幾乎平行類包含t＋1個26圈.最后剩余的是1）中的一個平行類包含兩個圈，構成短平行類.

定理3 階為n的推廣的幾乎可分解的26圈系的譜為n≡13（mod 52）.

證明 例1，3考慮了階為65和117的情況.52t＋3的構造給出了每一個階為n≡13（mod 52）（n≥117）的幾乎可分解的26圈系.因此，定理得證.

［1］ ALSPACH B，GAVLAS H.Cycle decompositions of and［J］.J Combin Theory B Ser，2001，81（1）：77-99.

［2］ SAJNA M.Cycle decompositions：Complete graphs and fixed length cycles［J］.J Combin Designs，2002，10（1）：27-78.

［3］ ALSPACH B，SCHELLENBERG P J，STINSON D R，et al.The Oberwolfach problem and factors of uniform odd length cycles［J］.J Combin Theory A Ser，1989，52（1）：20-43.

［4］ PIOTROWSKI W L.The solution of the bipartite analogue of the Oberwolfach problem［J］.Discrete Math，1991，97（3）：339-356.

［5］ VANSTONE S A，STINSON D R，SCHELLENBERG P J，et al.Hanani triple systems［J］.Israel J Math，1993，83（3）：305-319.

［6］ LINDNER C C，MESZKA M，ROSA A.Almost resolvable cycle systems：An analogue of Hanani triple systems［J］.J Combin Designs，2009，17（5）：404-410.

［7］ PETER A，ELIZABETH J B，HOFFMAN D G，et al.The generalized almost resolvable cycle system problem［J］.J Combin Math，2010，30（6）：617-625.

［8］ DEJTER I J，LINDNER C C，MESZKA M，et al.Almost resolcable 26-cycle systems［J］.J Combin Math Combin Computing，2007，63（2）：173-182.

［9］ LINDNER C C，RODGER C A.Design theory［M］.Bocaraton：CRC Press，1997：137-159.