摘要
设G=G(n,p)是一个随机图,其顶点数为n,任两个顶点之间有边相关联的概率为p=p(n),k是一个正整数满足k<np-2(nplogn)^(1/2).图G的—个支撑子图F称作是图G的—个[k,k+1卜因子,如果对任一个x∈V(G),都有k≤dF(x)≤k+1.我们证明任意满足p≥n^(-2/3)的随机图G(n,p)几乎一定包含[k,k+1]-因子.
Let G = G(n,p) be a binomial random graph with n vertices and edge probability p = p(n), and let k be a positive integer such that k〈np-2√nplogn.A spanning subgraph F of G is called a [k, k + 1]-factor if k≤dF(x)≤k+1 for every x ∈ V(G). In this paper, we proved that for any binomial random graph G(n,p) with p≥n^-2/3almost surely contains a [k, k + 1]-factor.
作者
蔡建生
闫桂英
CAI JIANSHENG YAN GUIYING(School of Mathematics and Information Science, Weifang University, Weifang 261061, China Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing 100190, China)
出处
《应用数学学报》
CSCD
北大核心
2017年第1期144-148,共5页
Acta Mathematicae Applicatae Sinica
基金
国家自然科学基金(11571258
11371355)
山东省自然科学基金(ZR2013AM001)资助项目