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 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 ： Gn,p be a binomial random graph with n vertices and edge probability p = p（n）, and f be a nonnegative integer-valued function defined on V（G） such that 0 〈 a ≤ f（x） ≤ b 〈 np- 2√nplogn for every ...Let G ： Gn,p be a binomial random graph with n vertices and edge probability p = p（n）, and f be a nonnegative integer-valued function defined on V（G） such that 0 〈 a ≤ f（x） ≤ b 〈 np- 2√nplogn for every E V（G）. An fractional f-indicator function is an function h that assigns to each edge of a graph G a number h（e） in [0, 1] so that for each vertex x, we have d^hG（x） = f（x）, where dh（x） = ∑ h（e） is the fractional degree xEe ofx inG. Set Eh = {e ： e e E（G） and h（e） ≠ 0}. IfGh isaspanningsubgraphofGsuchthat E（Gh） = Eh, then Gh is called an fractional f-factor of G. In this paper, we prove that for any binomial random graph Gn,p 2 with p 〉 n^-2/3, almost surely Gn,p contains an fractional f-factor.展开更多
基金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.
基金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 NSFSD(No.ZR2013AM001)NSFC(No.11001055),NSFC11371355
文摘Let G ： Gn,p be a binomial random graph with n vertices and edge probability p = p（n）, and f be a nonnegative integer-valued function defined on V（G） such that 0 〈 a ≤ f（x） ≤ b 〈 np- 2√nplogn for every E V（G）. An fractional f-indicator function is an function h that assigns to each edge of a graph G a number h（e） in [0, 1] so that for each vertex x, we have d^hG（x） = f（x）, where dh（x） = ∑ h（e） is the fractional degree xEe ofx inG. Set Eh = {e ： e e E（G） and h（e） ≠ 0}. IfGh isaspanningsubgraphofGsuchthat E（Gh） = Eh, then Gh is called an fractional f-factor of G. In this paper, we prove that for any binomial random graph Gn,p 2 with p 〉 n^-2/3, almost surely Gn,p contains an fractional f-factor.
