×

On the existence of \(\left[ {k,k + 1} \right]\)-factors in random graphs. (Chinese. English summary) Zbl 1389.05162

Summary: Let \(G = G\left({n, p} \right)\) be a binomial random graph with \(n\) vertices and edge probability \(p = p\left(n \right)\), and let \(k\) be a positive integer such that \(k < np - 2\sqrt {np\log n} \). A spanning subgraph \(F\) of \(G\) is called a \(\left[ {k, k + 1} \right]\)-factor if \(k \leq {d_F}\left(x \right) \leq k + 1\) for every \(x \in V\left(G \right)\). In this paper, we proved that for any binomial random graph \(G\left({n, p} \right)\) with \(p \geq {n^{ - \frac{2}{3}}}\), it almost surely contains a \(\left[ {k, k + 1} \right]\)-factor.

MSC:

05C80 Random graphs (graph-theoretic aspects)