Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651940 | Electronic Notes in Discrete Mathematics | 2015 | 9 Pages |
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(logn/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−1logn} vertices not in triangles.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics