(0,mf-m+1)图的正交(0,f)因子分解.docVIP

(0,mf-m+1)图的正交(0,f)因子分解 　　摘要：设G是一个图，f是定义在V(G)上的整数值函数，且对?坌x∈V(G)，有2k≤f(x)，设H1,H2,…,Hk是G的k个顶点不相交的子图，且|E(Hi)|=m，1≤i≤k，证明了每个(0,mf-m+1)图有一个(0,f)因子分解正交于Hi(i=1,2,…,k)。 　　关键词：图；因子；因子分解；正交因子分解 　　中图分类号：TP301文献标识码：A文章编号：1009-3044(2011)04-0820-01 　　Orthogonal (0,f) Factorizations of (0,mf-m+1) Graphs 　　LIU Jin-bo1,2, LIU Gang2, SUN Zhi-hong2 　　(1.College of Science, China University of Mining and Technology, Xuzhou 221008, China; 2.Department of Basic Cource Xuzhou Airforce College, Xuzhou 221000, China) 　　Abstract: Let G be a graph and f be an integer function defined on the vertices set V(G), such that 2k≤f(x) for every vertex x∈V(G), Let H1,H2,…,Hk be k vertex disjiont subgraphs of G such that |E(Hi)|=m，1≤i≤k,In this paper, it is proved that every (0,mf-m+1) graph G has a (0,f)factorizations Orthogonal to Hi, for i=1,2,…,k. 　　Key words: graph; factor; factorization; orthogonal factorization 　　本文所考虑的图皆为有限无向简单图。设图G是一个图，分别用V(G)和E(G)表示图G的顶点集和边集,用dG(x)表示x在G中的次数。设g和f是定义在V(G)上的非负整数值函数，且对任一x∈V(G)，有g(x)≤f(x)。G的一个(g,f)-因子是指 的一个支撑子图F，使得g(x)≤dF(x)≤f(x)对所有的x∈V(G)成立。若图 的边集能划分为m个边不交的(g,f)因子F1,F2,…,Fm，则称F={F1,F2,…,Fm}是图G的一个(g,f)-因子分解。具有m条边的子图称为mˉ子图。 　　文献[3-1]给出了(mg+m-1,mf-m+1)-图G有一个(g,f)-因子分解。文献[2]已证明：设G是一个(0,mf-m+1)-图，则对任意给定的m-子图， 都有一个(0,f)-因子分解。文献[3]已证明：若对任意x∈V(G)，都有2k≤f(x)，则每个(0,mf-m+1)图G有一个(0,f)-因子分解。本文进一步研究了(0,mf-m+1)图G的正交因子分解问题。证明如下结论：若对任意x∈V(G)，都有2k≤f(x)，则图G的(0,f)-因子分解一定正交于k个顶点不相交的mˉ子图。 　　1 预备引理 　　下面总假设G是一个(0,mf-m+1)-图，设S，T是V（G）的不相交子集，用EG(S,T)表示G中连接S及T的边集，记 　　引理1[1]：设G是一个(0,mf-m+1)-图，f(x)是定义在V（G）上的非负整数函数，H是G的mˉ子图， 　　则图G有一个(0,f)因子分解正交于H。 　　引理2[2,4]：设G 是一个图，g和f是定义在V(G)上的两个整数值函数且对每个x∈V(G)有0≤g(x) f(x)，E1和E2是E(G)的两个不相交子集，则图G有一个(g,f)因子F，使得E1?哿E(F)。 　　引理3[3,5]：设G是一个(0,mf-m+1)-图，f(x)是定义在V（G）上的整数值函数且对每个x∈V(G)有2k≤f(x)，这里m≥2,k≥2是整数，则图G有一个(0,f)因子F使得E1?哿E(F)且E2∩E(F)=Φ。 　　2 定理及证明 　　定理1：设G是一个(0,mf-m+1)-图，f(x)是定义在V（G）上的整数值函数，设H1,H2,…,Hk是G的k个顶点不相交的mˉ子图，则G有一个(0,f)因子分解正交于Hi(i=1,2,…,k)。 　　下面完成定理1的证明： 　　证明：当k=1时，由引理1知，定理显然成立，故以下可假设k≥2当m=1时，定理显然成立。 　　假设定理对m-1成立，这里m≥2，由引理3可知，G有一个(g,f)因