A Note on the Existence of Fractional f-factors in Random Graphs

作     者：Jian-sheng CAI Xiao-yang WANG Gui-ying YAN 

作者机构：School of Mathematics and Information ScienceWeifang University Beijing Anzhen HospitalCapital Medical University Academy of Mathematics and System ScienceChinese Academy of Science 

出 版 物：《Acta Mathematicae Applicatae Sinica》 (应用数学学报（英文版）)

年 卷 期：2014年第30卷第3期

页      面：677-680页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0712[理学-科学技术史(分学科，可授理学、工学、农学、医学学位)] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Supported by NSFSD(No.ZR2013AM001) NSFC(No.11001055),NSFC11371355 

主　　题：random graph probabilistic method f-factor fractional f-factor 

摘      要：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.