具有(n,k)-正交的(g,f)-因子分解的子图.pdf

《具有(n,k)-正交的(g,f)-因子分解的子图.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第17卷第6期华东船舶工业学院学报(自然科学版>VO1.17NO.6Z003年1Z月JOurnalOfEastChinaShipbuildingInstitute(NaturalScienceEditiOn>Dec.Z003文章编号!1006-1088"Z003#06-00Z7-04具有（!，"）!正交的（#，$）!因子分解的子图周思中1!薛秀谦Z(1.华东船舶工业学院数理系江苏镇江Z1Z003;Z.中国矿业大学理学院江苏徐州ZZ1008>摘要!设G是一个图g和f是定义在V(G>上的两个整数函数且对每个JeV(G>有g＜f本文证明了如下结果C设k是一个正整数G是一个(mg+nk

2、mf-nk>-图其中1＜n＜m~是G的任意一个有nk条边的子图若对每个JeV(G>有g）k则G中存在子图RR具有(gf>-因子分解与~(nk>-正交关键词!图;子图;因子;因子分解;(nk>-正交中图分类号!0157.5文献标识码!ASubgraphswith(!">!Orthogonal(#$>!Factorizations1XUEXiu-lianZZ~OUSi-zhong(1.Dept.OfMathematicsandPhysicsEastChinaShipbuildingInstituteZheniangJiangsuZ1Z003China;Z.COllegeOfScie

3、ncesChinaUniversityOfMiningandTechnOlOgyXuzhOuJiangsuZZ1008China>AbstractCLetGbeagraphandletg(J>andf(J>betwOinteger-valuedfunctiOnsdefinedOnthever-texsetV(G>OfagraphGsuchthatg(J>＜f(J>fOreveryJeV(G>.ThispapersuppOsesthatkisapOsitiveintegerGisan(mg+nkmf-nk>-graph1＜n＜m~isanysubgraphwithnkedgesO

4、fagraphG.Ifg）kfOreveryJeV(G>thenthereexistsasubgraphRingraphGRhasa(gf>-factOri-zatiOn(nk>-OrthOgOnaltO~.KeywordsCgraph;subgraph;factOr;factOrizatiOn;(nk>-OrthOgOnal0引言本文所考虑的图均指有限无向简单图设G是一个图分别用V(G>和E(G>表示图G的顶点集和边集对于JeV(G>用d(J>表示顶点J在G中的次数设g和f分别是定义在V(G>上的非负整值G函数使g(J>＜f(J>对所有JeV(G>成立则图G的一个(gf>-因

5、子是图G的一个支撑子图F使对任意的JeV(G>有g(J>＜d(J>＜f(J>特别地若G本身是一个(gf>-因子则称G为(gf>-F图若图G的边集能划分为t个边不相交的(gf>-因子FFF则F=FFF称为图G1Zt1Zt的一个(gf>-因子分解设~和F分别是图G的子图和因子分解且IE(~>I=tk若对所有1＜i＜t有IE(~>nE(Fi>I=k则称F和~(tk>-正交其它未加说明的概念和记号见参考文献1收稿日期!Z003-07-30作者简介!周思中(1975->男安徽桐城人华东船舶工业学院助教(硕士>Z8华东船舶工业学院学报(自然科学版>Z003年文ZI证明了一个(mg+kmf-

6、k>-图G1＜k＜m其中g(J>）1或f(J>）5则G中存在一个子图R满足对G的任意子图~IE(~>I=kR有(gf>-因子分解与~正交并提出如下猜想:设G是一个(mg+kmf-k>-图1＜k＜m其中对任意的JeV(G>0＜g(J>＜f(J>是定义在V(G>上的整数值函数则G存在一个子图R满足对G的任意子图~IE(~>I=kR有(gf>-因子分解与~正交0文3I和文4I独立地证明了该猜想成立0文5I证明了每个(mg+kmf-k>-图有k个边不相交的(gf>-因子正交于~IE(~>I=k1＜i＜0文6I证明了如果G是一个(mg+nmf-n>-ii图1＜n＜m＜Zk且g）Zk-1对

7、所有的点JeV(G>都成立则对任意给定具有IE(~>I=nk边的G的子图~存在G的一个子图G使得G有一个(gf>-因子分解与~(nk>-正交0本文证明了(mg+nkmf-nk>-图中存在子图RR是(nk>-正交的(gf>-可因子化图01预备引理设g和f是定义在V(G>上的两个非负整值函数使g＜f对所有JeV(G>成立又设S是V(G>的两个不交子集0记!G(gf3S>=f(S>-g(>+dG-S(>其中G-S表示从G中去掉顶点集S及与S关联的所有边所得的子图0f(S>=】f(J>g(>=】g(