Carnegie Mellon University
Browse
file.pdf (262.83 kB)

On the Non-Planarity of a Random Subgraph

Download (262.83 kB)
journal contribution
posted on 2013-06-24, 00:00 authored by Alan FriezeAlan Frieze, Michael Krivelevich

Let G be a finite graph with minimum degree r. Form a random subgraph Gp of G by taking each edge of G into Gpindependently and with probability p. We prove that for any constant ε > 0, if , then Gp is non-planar with probability approaching 1 as r grows. This generalizes classical results on planarity of binomial random graphs.

History

Publisher Statement

© Cambridge University Press

Date

2013-06-24

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC