完全二部多重圖的K2,3-因子分解

朱 莉,王 建

(南通職業大學基礎部,江蘇南通 226007)

完全二部多重圖的K2,3-因子分解

朱 莉,王 建

(南通職業大學基礎部,江蘇南通 226007)

如果完全二部多重圖Km,n的邊集可以劃分為Km,n的Kp,q-因子,則稱Km,n存在Kp,q-因子分解.當p=1和q=2時,Km,n的K1,2-因子分解的存在性問題已被完全解決.最近我們得到了當=1時,Km,n存在K2,3-因子分解的充分必要條件.對于任意正整數,本文證明完全二部多重圖Km,n存在K2,3-因子分解的充分必要條件是(i)2m≤3n,(ii)2n≤3m,(iii)m+n≡0(mod 5),(iv)5mn/[6(m+n)]是整數.

二部多重圖;因子;因子分解

1 引 言

Km,n表示完全二部圖,其兩個部分點集X和Y分別具有m和n個點.Km,n表示完全二部多重圖,

它是個兩兩不交的同構于Km,n的圖的并.如果Km,n的一個子圖F包含了Km,n的所有點,則稱F為Km,n的一個支撐子圖.若Km,n的支撐子圖F的每個分支均同構于圖Kp,q,則稱F為Km,n的一個Kp,q-因子.如果Km,n的邊集可以劃分為Km,n的Kp,q-因子,則稱Km,n存在Kp,q-因子分解.在綜述文章[1]中,Ushio稱Km,n的Kp,q-因子分解為可分解的(m,n,k,)二部Kp,q-設計.如果Km,n存在Kp,q-因子分解,則稱Km,n是可Kp,q-因子分解的.本文用到的圖論方面的名詞術語,均參照圖論著作[2].

Km,n的Kp,q-因子分解有許多應用,特別是Yamamoto和Ushio等[3]用其建立了計算機數據存儲的HUBMFS2方案.當p=1和q=2時,Ushio[4]完全解決了=1情形下Km,n的K1,2-因子分解的存在性問題.在論文[5]中,我們完全解決了＞1情形下Km,n的K1,2-因子分解的存在性問題.當p=2和q=3時,我們在論文[6]中完全解決了Km,n的K2,3-因子分解的存在性.本文將給出完全二部多重圖Km,n存在K2,3-因子分解充分必要條件.即我們證明

定理1.1 完全二部多重圖Km,n存在K2,3-因子分解的充分必要條件是(i)2m≤3n,(ii)2n≤3m, (iii)m+n≡0(mod 5),(iv)5mn/[6(m+n)]是整數.

2 定理1.1的證明

定理1.1的必要性證明通過簡單計算即可得到,充分性部分的證明由以下幾個引理構成,第一個引理是顯然的,其中gcd(x,y)表示x和y的最大公約數.

引理2.1 設u,v,x和y是正整數.如果gcd(ux,vy)=1,則gcd(uv,ux+vy)=1.

引理2.2 設s是任意正整數.如果Km,n存在K2,3-因子分解,則s Km,n存在K2,3-因子分解.

證重復Km,n的K2,3-因子分解s次即得s Km,n的K2,3-因子分解.

引理2.3 設s是任意正整數.如果Km,n存在K2,3-因子分解,則Kms,ns存在K2,3-因子分解.

證 由于Ks,s是可1-因子分解的[2],可設{Fi∶1≤i≤s}是它的一個1-因子分解.對于每一個1≤i≤s,用Km,n代替Fi的每條邊,即得到Kms,ns的一個支撐子圖Gi,且Gi(1≤i≤s)邊集的并為Kms,ns.由于

Km,n是可K2,3-因子分解的,因而Gi也是可K2,3-因子分解的.所以Kms,ns存在K2,3-因子分解.

由引理2.3我們易得當2m=3n或2n=3m時,Km,n存在K2,3-因子分解.因此下面只需考慮2m＜3n且2n＜3m時的情形.在這種情形下,令a=(3n-2m)/5,b=(3m-2n)/5,t=(m+n)/5和r=5mn/[6(m+n)].由定理1.1的條件(i)-(iv)可知a,b,t,r是整數,且0＜a＜m,0＜b＜n.于是有2a+3b=m,3a+2b=n.進而可得r=(a+b)+ab/[6(a+b)].設z=ab/[6(a+b)],它也是整數.設gcd(2a,3b)=d,2a=dp,3b=dq,其中gcd(p,q)=1.因此z=dpq/[6(3p+2q)].于是可得下列各式:

[1] Ushio K.G-designs and related designs[J].Discrete Math.,1993,116(1)：299-311.

[2] Harary F.Graph theory[M].Massachusetts：Addison-Wesley,1972.

[3] Yamamoto S,Tazawa S,Ushio K,Ikede H.Design of a generalized balanced multiple-valued file organization scheme with the least redundancy[J].ACM Trans.Database Systems,1979,4(2)：518-530.

[4] Ushio K.P3-factorization of complete bipartite graphs[J].Discrete Math.,1988,72(4)：361-366.

[5] Wang J,Du B L.P3-factorization of complete bipartite multigraphs and symmetric complete bipartite multi-digraphs[J]. Util.Math.,2003,63(4)：213-228.

[6] Wang J,Du B L.Kp,q-factorization of the complete bipartite graph Km,n[J].Discrete Math.,2004,283(4)：283-287.

K2,3-factorization of Complete Bipartite Multigraphs

Z HU L i,WA N G J ian

(Nantong Vocational College,Nantong 226007,China)

LetKm,nbe acomplete bipartite multigraph with two partite sets havingmandnvertices,respectively.A Kp,q-factorization ofKm,nis a set of edge-disjointKp,q-factors ofKm,n.Whenp=1 andq=2,theK1,2-factorization of

Km,nhas been completely solved.Recently,we gave a necessary and sufficient condition forK2,3-factorization ofKm,n.In this article,we will give a necessary and sufficient condition forK2,3-factorization ofKm,nis that(i)2m≤3n, (ii)2n≤3m,(iii)m+n≡0(mod 5)and(iv)5mn/[6(m+n)]is an integer.

complete bipartite multigraphs;factor;factorization

O157

A

1672-1454(2011)03-0070-05

2008-07-01;[修改日期]2009-01-20

江蘇省高校自然科學基金資助項目(04KJD110152)