二分图中具有正交(g,f)-因子分解的子图

Subgraph with Orthogonal (g,f)-Factorizations in Bipartite Graph

设G是一个二分的(mg+k,mf-k) 图,其中1≤k<m,g(x)和f(x)是定义在V(G)上的整数值函数,且 x∈V(G)有r2≤g(x)<f(x),H1,H2,…,Hr是G的r个顶点不相交的子图,且E(Hi)=k(1≤i≤r).本文证明了G存在一个子图R,使得R有(g,f) 因子分解与Hi正交(1≤i≤r).

Let G be a bipartite (mg(x)+k,mf(x)-k)graph,1≤k<m,and let g(x) and f(x) be two integervalued functions defined on V(G) such that r2≤g(x)<f(x) for every x∈V(G).Let H1,H2,...,Hr be r subgraphs of G such that E(Hi)=k,1≤i≤r.In this paper,it is proved that there exists a subgraph R which has a (g,f)factorization orthogonal to Hi(1≤i≤r).