二分图上有限制条件的(g,f)-因子和f-因子  

(g,f)-Factors and f-factors with constraints in bipartite graphs

作　　者：侯建锋[1] 王纪辉[2] 刘桂真[1] 

机构地区：[1]山东大学数学与系统科学学院,山东济南205100 [2]济南大学理学院,山东济南250022

出　　处：《山东大学学报（理学版）》2006年第2期48-51,共4页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金资助项目(10471078);教育部博士点专项科研基金资助项目(20040422004)

摘　　要：设图G=(X,Y,E)是二分图,g,f是定义在V(G)上的正整值函数,且对任意的x∈V(G)有g(x)<f(x),证明了:如果图G是(mg,mf-1)-图,M是G的任一含有m条边的对集,则存在图G的一个(g,f)-因子F,使F包含M任意给定的一条边,并且不包含其他的m-1条边;二分图G是(2m-1)-边连通的(mf)-图,则图G有一个f-因子包含任意给定的一条边,并且不包含任意其他的m-1条边.Let G = （ X, Y, E） be a bipartite graph and let g and f be two positive integer functions defined on V（G） with g（x） 〈 f（x） for each x ∈ V（G）. It is proved that if a G is the （ mg, mf- 1 ）- graph and M is a mathing with m edge, then G has a （g,f）-factor containing an edge of M and excluding other edges of M. If G is the （2m - 1）-edge connected bipartite （ mf）-graph, then G has an f factor containing any given edge and excluding any given m - 1 edges.

关 键 词：二分图 (G F)-因子 F-因子 (g f)-可因子化 

分 类 号：O157.5[理学—数学]