On the non-planarity of a random subgraph

DOI10.1017/S0963548313000308MaRDI QIDQ5397728zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael Krivelevich, Alan Frieze

Publication date 24 February 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.6240

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let $G$ be a finite graph with minimum degree $r$. Form a random subgraph $G_p$ of $G$ by taking each edge of $G$ into $G_p$ independently and with probability $p$. We prove that for any constant $epsilon>0$, if $p=frac1+epsilonr$, then $G_p$ is non-planar with probability approaching 1 as $r$ grows. This generalizes classical results on planarity of binomial random graphs.

Recommendations

• On the Number of Edges in Random Planar Graphs
• Spanning maximal planar subgraphs of random graphs
• On the probability that a random subgraph contains a circuit
• Large complete minors in random subgraphs
• Maximal planar subgraphs of fixed girth in random graphs

Cited in

(9)

• Towards the distribution of the size of a largest planar matching and largest planar subgraph in random bipartite graphs
• Maximal planar subgraphs of fixed girth in random graphs
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• Small subgraphs in random distance graphs
• On random k-out subgraphs of large graphs
• scientific article; zbMATH DE number 4112650 (Why is no real title available?)
• Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs
• On the probability that a random subgraph contains a circuit
• Large complete minors in random subgraphs

This page was built for publication: On the non-planarity of a random subgraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5397728)