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

蒲利群，方佳，馬俊

（1.鄭州大學(xué) 數(shù)學(xué)系，河南 鄭州450001；2.上海交通大學(xué) 數(shù)學(xué)系，上海200240）

1 基本知識(shí)

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

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

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

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

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

2 三個(gè)基本構(gòu)造

給出的3個(gè)例子是構(gòu)造26GARCS（n）的基礎(chǔ).其中：V（G）表示圖G的點(diǎn)集；Kn表示階為n的完全圖；Km，n表示兩個(gè)部分的點(diǎn)集數(shù)分別為m和n的完全二部圖.

例1 26GARCS（65）

令點(diǎn)集V（K65）＝｛ij｜i∈Z13，j＝1，2，3，4，5，有40個(gè)幾乎平行類(lèi).13個(gè)幾乎平行類(lèi)是在模13下循環(huán)，其下標(biāo)被固定為

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

集合F1含下面的兩個(gè)幾乎平行類(lèi)，該平行類(lèi)在模13下循環(huán)，其下標(biāo)固定為

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

例3 26GARCS（117）

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

兩個(gè)幾乎平行類(lèi)在模13下循環(huán)，其下標(biāo)是固定的，即

以上26個(gè)幾乎平行類(lèi)使用了所有的純差和部分的混差，剩余的混差下標(biāo)，如表1所示.因下標(biāo)相同的兩個(gè)混差可構(gòu)造一個(gè)26圈，表1由包含4對(duì)下標(biāo)的列和包含一對(duì)下標(biāo)列組成.

表1 剩余混差的下標(biāo)Tab.1 Remaining mixed difference subscript

使用相同的方法可構(gòu)造其他所有的幾乎平行類(lèi).

2 構(gòu)造26GARCS（n）s

為了證明主要的結(jié)果，需要定理2.

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

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

Ⅲ）現(xiàn)在已經(jīng)窮盡了3）中的所有26圈，剩余的圈集有1）中的14個(gè)幾乎平行類(lèi)，F(xiàn)2中12個(gè)幾乎平行類(lèi)和對(duì)每一個(gè)hi，2≤i≤t的S中的短平行類(lèi).由于F2中的幾乎平行類(lèi)與洞∞中的點(diǎn)不相交，將1）中12個(gè)幾乎平行類(lèi)與每一個(gè)洞hi，i≥2，F(xiàn)2中的12個(gè)幾乎平行類(lèi)配對(duì).則得到C中的12個(gè)幾乎平行類(lèi).

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

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

證明 例1，3考慮了階為65和117的情況.52t＋3的構(gòu)造給出了每一個(gè)階為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.