×

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

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)
PDF BibTeX XML Cite
Full Text: EuDML