随机图中[k,k+1]-因子的存在性

On the Existence of[k,k+1]-factors in Random Graphs

设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.