کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651940 1632582 2015 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Local resilience of spanning subgraphs in sparse random graphs
ترجمه فارسی عنوان
انعطاف پذیری محلی از زیرگرافها در نمودارهای تصادفی اسپا
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 513-521