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

朱 莉,王 建

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

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

朱 莉,王 建

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

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

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

1 引 言

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

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

Km,n的Kp,q-因子分解有許多應(yīng)用,特別是Yamamoto和Ushio等[3]用其建立了計(jì)算機(jī)數(shù)據(jù)存儲(chǔ)的HUBMFS2方案.當(dāng)p=1和q=2時(shí),Ushio[4]完全解決了=1情形下Km,n的K1,2-因子分解的存在性問題.在論文[5]中,我們完全解決了＞1情形下Km,n的K1,2-因子分解的存在性問題.當(dāng)p=2和q=3時(shí),我們在論文[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)]是整數(shù).

2 定理1.1的證明

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

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

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

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

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

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

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

由引理2.3我們易得當(dāng)2m=3n或2n=3m時(shí),Km,n存在K2,3-因子分解.因此下面只需考慮2m＜3n且2n＜3m時(shí)的情形.在這種情形下,令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是整數(shù),且0＜a＜m,0＜b＜n.于是有2a+3b=m,3a+2b=n.進(jìn)而可得r=(a+b)+ab/[6(a+b)].設(shè)z=ab/[6(a+b)],它也是整數(shù).設(shè)gcd(2a,3b)=d,2a=dp,3b=dq,其中g(shù)cd(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

江蘇省高校自然科學(xué)基金資助項(xiàng)目(04KJD110152)