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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.endm.2015.06.071 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
extremal graph theory,random graphs,sparse regularity,resilience | Discrete mathematics,Random regular graph,Combinatorics,Random graph,Graph labeling,Cycle graph,Degree (graph theory),Symmetric graph,Mathematics,Path graph,Complement graph | Journal |
Volume | ISSN | Citations |
49 | 1571-0653 | 1 |
PageRank | References | Authors |
0.36 | 8 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Peter Allen | 1 | 9 | 2.91 |
Julia Böttcher | 2 | 93 | 17.35 |
Julia Ehrenmüller | 3 | 7 | 2.67 |
Anusch Taraz | 4 | 168 | 37.71 |