亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2011-11-22 01:36:48莉,王
        大學數學 2011年3期

        朱 莉,王 建

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

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

        朱 莉,王 建

        (南通職業(yè)大學基礎部,江蘇南通 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)

        边喂奶边中出的人妻| 92自拍视频爽啪在线观看| 男人的精品天堂一区二区在线观看| 国产精品美女久久久免费| 精产国品一二三产品蜜桃| 日本一卡二卡3卡四卡免费观影2022| 55夜色66夜色国产精品视频| 欧美a视频在线观看| 在线视频一区二区观看| 国产av一区二区三区在线播放| 亚洲精品国偷拍自产在线观看| 精品国产午夜福利在线观看| 伊人色综合九久久天天蜜桃 | 亚洲人成网站18禁止| 亚洲综合无码无在线观看| 91精品全国免费观看青青| 国产成人一区二区三区高清| 国产另类av一区二区三区| 77777_亚洲午夜久久多人| 日本老熟欧美老熟妇| 国产精品不卡无码AV在线播放| 无人视频在线播放免费| 欧美日韩一区二区三区在线观看视频| 中文字幕精品久久久久人妻红杏1 丰满人妻妇伦又伦精品国产 | 天堂资源中文最新版在线一区| 综合无码一区二区三区四区五区| 一区两区三区视频在线观看| 久久天天躁狠狠躁夜夜av浪潮| 制服丝袜中文字幕在线| 日韩欧美亚洲综合久久影院d3| 亚洲精品中文字幕乱码二区| 国产自拍av在线观看| 日本va欧美va精品发布| 久久婷婷色综合一区二区| 精品日本韩国一区二区三区| 大香焦av一区二区三区| 精品人妻无码一区二区三区蜜桃一 | 妺妺窝人体色www在线图片 | 中文字幕一区二区三区亚洲| 日本五十路人妻在线一区二区| 久久精品无码一区二区三区免费|