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.展开更多
In this paper the properties of some maximum fractional [0, k]-factors of graphs are presented. And consequently some results on fractional matchings and fractional 1-factors are generalized and a characterization of ...In this paper the properties of some maximum fractional [0, k]-factors of graphs are presented. And consequently some results on fractional matchings and fractional 1-factors are generalized and a characterization of fractional k-factors is obtained.展开更多
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.展开更多
Let G be a graph, and g, f ： V（G）→Z＋ with g（x） 〈 f（x） for each x ∈ V（G）. We say that G admits all fractional （g, f）-factors if G contains an fractional r-factor for every r ： V（G）→ Z＋ with g（x） ...Let G be a graph, and g, f ： V（G）→Z＋ with g（x） 〈 f（x） for each x ∈ V（G）. We say that G admits all fractional （g, f）-factors if G contains an fractional r-factor for every r ： V（G）→ Z＋ with g（x） ≤ r（x） ≤ f（x） for any x ∈ V（G）. Let H be a subgraph of G. We say that G has all fractional （g, f）-factors excluding H if for every r ： V（G） → Z＋ with g（x） ≤ r（x） ≤ f（x） for all x ∈ V（G）, G has a fractional r-factor Fh such that E（H） ∩ E（Fh） = Ф, where h ： E（G） → [0, 1] is a function. In this paper, we show a characterization for the existence of all fractional （g, f）-factors excluding H and obtain two sufficient conditions for a graph to have all fractional （g, f）-factors excluding H.展开更多
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.展开更多
基金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.
基金This work is supported by NSFC (10471078.10201019)RSDP (20040422004) of China
文摘In this paper the properties of some maximum fractional [0, k]-factors of graphs are presented. And consequently some results on fractional matchings and fractional 1-factors are generalized and a characterization of fractional k-factors is obtained.
基金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.
基金supported by the National Natural Science Foundation of China(Grant No.11371009,11501256,61503160)sponsored by Six Big Talent Peak of Jiangsu Province(Grant No.JY–022)333 Project of Jiangsu Province
文摘Let G be a graph, and g, f ： V（G）→Z＋ with g（x） 〈 f（x） for each x ∈ V（G）. We say that G admits all fractional （g, f）-factors if G contains an fractional r-factor for every r ： V（G）→ Z＋ with g（x） ≤ r（x） ≤ f（x） for any x ∈ V（G）. Let H be a subgraph of G. We say that G has all fractional （g, f）-factors excluding H if for every r ： V（G） → Z＋ with g（x） ≤ r（x） ≤ f（x） for all x ∈ V（G）, G has a fractional r-factor Fh such that E（H） ∩ E（Fh） = Ф, where h ： E（G） → [0, 1] is a function. In this paper, we show a characterization for the existence of all fractional （g, f）-factors excluding H and obtain two sufficient conditions for a graph to have all fractional （g, f）-factors excluding H.
基金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.
