Planarity thresholds for two types of random subgraphs of the n-cube. (English) Zbl 0679.05062

Mahrhold, Karin; Weber, Karl

Commentat. Math. Univ. Carol. 30, No. 1, 71-73 (1989).

Consider a random spanning (respectively induced) subgraph of the n-cube \(Q_ n\) in which each edge (respectively vertex) is present with probability p, it is shown that \(2^{-n/14_ n-4/14}\) (respectively \(2^{-n/11}n^{-4/11})\) is the threshold probability for the planarity of this random graph.

Reviewer: G.Grimmett

MSC:

05C80

Random graphs (graph-theoretic aspects)

Keywords:

random graph; planarity