图中推广的正交因子分解

设G是一个图,具有顶点集合V(G)和边集合E(G).设g和f是定义在V(G)上的整数值函数,使对每个x∈V(G),有g(x)≤f(x).图G的一个(g,f)-因子是G的一个支撑子图H,使对每个x∈V(G),有g(x)≤d_H(x)≤f(x).G的一个(g,f)-因子分解是E(G)的边不相交的(g,g)-因子的一个划分.设F={F-1,F_2,…,F_m}为G的一个因子分解,H是G的一个有mr条边的子图.如果每个F_i恰好与H有r条公共边,1≤i≤m,则称Fr-正交于H.本文证明每个(mg+kr,mf-kr)-图含有一个子图R,使R有(g,f)-因子分解r-正交于任意给定的有kr条边的子图,其中m,k和r为正整数且k

A Generalization of Orthogonal Factorizations in Graphs

In this paper, let G be a graph with vertex set V(G) and edge set E(G), and let g and f be two integer-valued functions defined on V(G) such that g(x) ≤ f(x) for all ∈ 6 V(G). Then a (g,f)-factor of G is a spanning subgraph H of G such that g(x) ≤ dH(x) ≤ f(x) for all x ∈ V(G). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F - {F1, F2, ..., Fm} be a factorization of G, and H be a subgraph of G with mr edges. If Fi, 1 ≤ i ≤ m, has exactly r edges in common with H, then F is said to be r-orthogonal to H. In this paper it is proved that every (mg + kr, mf - kr)-graph, where m, k and r are positive integers with k < m and g ≥ r, contains a subgraph R such that R has a (g,f)-factorization which is r-orthogonal to a given subgraph H with kr edges.