摘要
设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<m,g≥r.
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.
出处
《数学学报（中文版）》
SCIE
CSCD
北大核心
2003年第4期715-720,共6页
Acta Mathematica Sinica：Chinese Series
基金
国家自然科学基金(19831080
60172003)
山东省自然科学基金(Z2000A02)
