朱 莉,陸 健
(南通職業(yè)大學(xué) 基礎(chǔ)部,江蘇 南通226007)
Km,n是完全二部圖,其兩個部分點集分別具有m和n個點表示對稱的完全二部有向圖,它是由Km,n的每條邊替換成方向相反的兩條有向弧而的到的有向圖表示2k長有向圈,其點集為向弧集為-因子是的一個子圖F,其滿足(1)F的有向弧集可分解為若干個有向圈,(2)的每一個點都恰好出現(xiàn)在 F 的α個中。如果的有向弧集可以劃分為-因子的和,則稱存在,α)-因子分解,或稱可-因子分解。本文用到圖論方面的名詞術(shù)語均參照圖論著作[1]或[2]。
證明:記 λ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.