×

\({K_4}\)-factors in random graphs. (Chinese. English summary) Zbl 1438.05226

Summary: For a graph \(G\) with \(n\) vertices, where 4 divides \(n\), a \(K_4\)-factor is a subgraph of \(G\), consisting of \(\frac{n}{4}\) vertex disjoint \(K_4\). The minimal probability \(p = p(n)\) for which a random graph \(G(n, p)\) almost surely contains a \(K_4\)-factor. For \(p = O(n^{-0.44})\), the random graph \(G(n, p)\) almost surely contains a \(K_4\)-factor.

MSC:

05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI