(0,mf-m+1)图的正交(0,f)因子分解
开篇：润墨网以专业的文秘视角，为您筛选了一篇(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)
引理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)因子F1使得E1?哿E(F1)且E2∩E(F1)=Φ。由g(x)的定义知，F1也是G的一个含E1而不含E2的(0,f)因子。
令G'=G-E(F1)，根据g(x)的定义，有
因此，G'是一个(0,(m-1)f-(m-1)+1)图。
令H'i=Hi-E1，1≤i≤k，根据归纳假设可知，G'有一个(0,f)因子分解F'={F2,…,Fm}正交于每个H'i, 1≤i≤k。于是，G有一个(0,f)因子分解F={F2,…,Fm}正交于每个Hi，1≤i≤k。
定理1证毕。
参考文献：
[1] Alspach B,Heinrich K,Liu G. Contemporary Design Theory a Collection of Surveys[M].New York:wiley,1998:145-148.
[2] Liu G, othogonal (g,f)factoizations in graphs[J].D is crete Math: 1997:78-91.
[3] 刘金波,刘刚,王淑玲.(0,mf-m+1)图的(0,f)因子分解[J].电脑知识与技术,2011(1).
[4] Liu G.othogonal (g,f)factoizations in graphs[J].D is crete Math,1997:104-110.
[5] Feng H.On orthogonal (0,f)factoizations [J].Actamath Scientia,1999,19:142-147.