完全二部有向圖的(，α)-因子分解

朱 莉，陸 健

(南通職業(yè)大學(xué) 基礎(chǔ)部，江蘇 南通226007)

0 引言

Km，n是完全二部圖，其兩個部分點集分別具有m和n個點表示對稱的完全二部有向圖，它是由Km，n的每條邊替換成方向相反的兩條有向弧而的到的有向圖表示2k長有向圈，其點集為向弧集為－因子是的一個子圖F，其滿足(1)F的有向弧集可分解為若干個有向圈，(2)的每一個點都恰好出現(xiàn)在 F 的α個中。如果的有向弧集可以劃分為－因子的和，則稱存在，α)－因子分解，或稱可－因子分解。本文用到圖論方面的名詞術(shù)語均參照圖論著作［1］或［2］。

1 主要結(jié)論

證明:記 λKm，n和 Y 是的兩個部分點集，且 | λKm，n|=m，|Y|=n。設(shè)的一－因子分解，其中Fi(1≤i≤r)是－因子。在每一個－因子 Fi(1≤i≤r)中，λKm，n中的每一個點和Y中的每一個點均出現(xiàn)α次。由 λKm，n中點計算－因子分解中，有－因子數(shù)得 r=n/α，再由 Y 中點計算，α)－因子數(shù)得 r=m/α，它們應(yīng)該相等。所以有，m=n ≡0(mod α)。在每一個－因子中，的數(shù)量有，即 b=nα/k。由 r和b的表達(dá)式，我們可得m=n≡0(modαk/d)，其中d是α和k的最大公約數(shù)。必要性得證。

證明:設(shè){F1，F(xiàn)2，...，F(xiàn)s}是Ks，s的一個1－因子分解(其存在性見文獻(xiàn)［1］)，其中 Fi(1≤i≤s)是 Ks，s的 1－因子。再設(shè)，其中的邊。將 Ks，s的每一個點加權(quán)n，每條邊ei，j看作是一個。由題設(shè)，令相對應(yīng)－因子分解，其中是相對應(yīng)－因子。則對于每一個是的一個－因子，而即是－因子分解。得證。

證明:令λKm，n和Y是的兩個部分點集，且

約定 xi和 yj的下標(biāo)在{1，2，...，αk/d}進(jìn)行模 αk/d 的運算。

對于任意1≤j≤n+1，構(gòu)造如下有限圈

則可以驗證每一個Fp(p∈Zp/d)都是－因子，且它們并集正好構(gòu)成。從而，{Fp|p∈Zp/d}是－因子分解。

［1］Harary F.Graph Theory［M］.Massachusetts:Addison-Wesley，1969.

［2］Chartrand G，Lesniak L.Graphs＆ Digraph［M］.2nded，California:Wadsworth，1986.

［3］Jungnickel D，Mullin R C，Vanstone.The spectrum ofα-resolvable block designs with block size 3［J］.Discrete Math，1991，97(4):269－277.

［4］Zhang Y，Du B.α-resolvable group divisible designs with block size three［J］.Combin.Designs，2005，13(1):139－151.

［5］Ma X W，Tian Z H.α-resolvable cycle systems for cycle length 4［J］.Journal of Mathematical Research＆ Exposition，2009，29(6):1102－1106.