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

被引：9

作者：

Cai, Jian-sheng ^{[1
]}

Wang, Xiao-yang ^{[2
]}

Yan, Gui-ying ^{[3
]}

机构：

[1] Weifang Univ, Sch Math & Informat Sci, Weifang 261061, Peoples R China

[2] Capital Med Univ, Beijing Anzhen Hosp, Beijing 100029, Peoples R China

[3] Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China

来源：

ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES | 2014年 / 30卷 / 03期

关键词：

random graph; probabilistic method; f-factor; fractional f-factor;

D O I：

10.1007/s10255-014-0411-y

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let G = G(n,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 root nplogn for every x epsilon 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(G)(h)(x) = f(x), where d(G)(h)(x) = Sigma(x epsilon e)h(e) is the fractional degree of x in G. Set E-h = {e : e epsilon E(G) and h(e) not equal 0}. If G(h) is a spanning subgraph of G such that E(G(h)) = E-h, then G(h) is called an fractional f-factor of G. In this paper, we prove that for any binomial random graph G(n,p) with p >= n(-2/3), almost surely G(n,p) contains an fractional f-factor.

引用

页码：677 / 680

页数：4