完全二部多重图的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)