Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G ...Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤ dH(x) 5 f(x) for each x ∈ V(H). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F = {F1, F2,…… ， Fm } and H be a factorization and a subgraph of G, respectively. If F, 1 ≤ i ≤ m， has exactly one edge in common with H, then it is said that ■ is orthogonal to H. It is proved that every bipartite (mg + m - 1, mf - m + 1 )-graph G has a (g, f)-factorization orthogonal to k vertex disjoint m-subgraphs of G if 2-k ≤ g(x) for all x ∈ V(G). Furthermore, it is showed that the results in this paper are best possible.展开更多
This paper presents a new proof of a charaterization of fractional (g, f)-factors of a graph in which multiple edges are allowed. From the proof a polynomial algorithm for finding the fractional (g, f)-factor can be i...This paper presents a new proof of a charaterization of fractional (g, f)-factors of a graph in which multiple edges are allowed. From the proof a polynomial algorithm for finding the fractional (g, f)-factor can be induced.展开更多
Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x).In this paper,some sufficient conditions related to the connectivity and edge-connec...Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x).In this paper,some sufficient conditions related to the connectivity and edge-connectivity for a bipartite (mg,mf)-graph to have a (g,f)-factor with special properties are obtained and some previous results are generalized.Furthermore,the new results are proved to be the best possible.展开更多
Let G be a graph with vertex set V(G) and edge set E(G) and let g and f betwo integer-valued functions defined on V(G) such that 2k - 2 ≤ g(x) ≤ f(x) for all x ∈ V(G).Let H be a subgraph of G with mk edges. In this...Let G be a graph with vertex set V(G) and edge set E(G) and let g and f betwo integer-valued functions defined on V(G) such that 2k - 2 ≤ g(x) ≤ f(x) for all x ∈ V(G).Let H be a subgraph of G with mk edges. In this paper, it is proved that every (mg + m - 1, mf - m +l)-graph G has (g, f)-factorizations randomly k-orthogonal to H under some special conditions.展开更多
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 2k-1≤g(x) ≤ f(x) for all x ∈ V(G). Let H be a subgraph of G with mk edges . In this ...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 2k-1≤g(x) ≤ f(x) for all x ∈ V(G). Let H be a subgraph of G with mk edges . In this paper it is proved that every (mg + m - 1,mf- m + 1)-graph G has (g, f)-factorizations randomly κ-orthogonal to H and shown that the result is best possible.展开更多
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 x ∈ V（G）. Then a （g, f）-factor of G is a spanning s...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 x ∈ V（G）. Then a （g, f）-factor of G is a spanning subgraph H of G such that g（x）≤d<sub>H</sub>（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={F<sub>1</sub>, F<sub>2</sub>...., F<sub>m</sub>} be a factorization of G, and H be a subgraph of G with mr edges. If F<sub>i</sub>. 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.展开更多
基金This work was supported by NNSF. RFDP and NNSF of shandong province(Z2000A02 ).
文摘Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤ dH(x) 5 f(x) for each x ∈ V(H). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F = {F1, F2,…… ， Fm } and H be a factorization and a subgraph of G, respectively. If F, 1 ≤ i ≤ m， has exactly one edge in common with H, then it is said that ■ is orthogonal to H. It is proved that every bipartite (mg + m - 1, mf - m + 1 )-graph G has a (g, f)-factorization orthogonal to k vertex disjoint m-subgraphs of G if 2-k ≤ g(x) for all x ∈ V(G). Furthermore, it is showed that the results in this paper are best possible.
基金This work is supported by NNSF of ChinaRFDP of Higher Education
文摘This paper presents a new proof of a charaterization of fractional (g, f)-factors of a graph in which multiple edges are allowed. From the proof a polynomial algorithm for finding the fractional (g, f)-factor can be induced.
基金Supported by the National Natural Science Foundation of China( 60 1 72 0 0 3) NSF of Shandongprovince ( Z2 0 0 0 A0 2 )
文摘Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x).In this paper,some sufficient conditions related to the connectivity and edge-connectivity for a bipartite (mg,mf)-graph to have a (g,f)-factor with special properties are obtained and some previous results are generalized.Furthermore,the new results are proved to be the best possible.
基金The work is partially supported by NNSF of China(10471078)RSDP of China
文摘Let G be a graph with vertex set V(G) and edge set E(G) and let g and f betwo integer-valued functions defined on V(G) such that 2k - 2 ≤ g(x) ≤ f(x) for all x ∈ V(G).Let H be a subgraph of G with mk edges. In this paper, it is proved that every (mg + m - 1, mf - m +l)-graph G has (g, f)-factorizations randomly k-orthogonal to H under some special conditions.
基金the National Natural Science Foundation of China (No.60172003,19831080) by NSF of Shandong Province.
文摘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 2k-1≤g(x) ≤ f(x) for all x ∈ V(G). Let H be a subgraph of G with mk edges . In this paper it is proved that every (mg + m - 1,mf- m + 1)-graph G has (g, f)-factorizations randomly κ-orthogonal to H and shown that the result is best possible.
基金This research is supported by the National Natural Science Foundation of China (19831080) and RSDP of China
文摘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 x ∈ V（G）. Then a （g, f）-factor of G is a spanning subgraph H of G such that g（x）≤d<sub>H</sub>（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={F<sub>1</sub>, F<sub>2</sub>...., F<sub>m</sub>} be a factorization of G, and H be a subgraph of G with mr edges. If F<sub>i</sub>. 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.
