Article ID Journal Published Year Pages File Type
4651940 Electronic Notes in Discrete Mathematics 2015 9 Pages PDF
Abstract

For each real γ>0 and integers Δ≥2 and k≥1, we prove that there exist constants β>0 and C>0 such that for all p≥C(log⁡n/n)1/Δ the random graph G(n,p) asymptotically almost surely contains – even after an adversary deletes an arbitrary (1/k−γ)-fraction of the edges at every vertex – a copy of every n-vertex graph with maximum degree at most Δ, bandwidth at most βn and at least Cmax⁡{p−2,p−1log⁡n} vertices not in triangles.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics