کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423902 1632593 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Largest sparse subgraphs of random graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Largest sparse subgraphs of random graphs
چکیده انگلیسی

For the Erdős-Rényi random graph Gn,p, we consider the order of a largest vertex subset that induces a subgraph with average degree at most t. For the case when both p and t are fixed, this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a result on the independence number of random graphs. For both the upper and lower bounds, we rely on large deviations inequalities for the binomial distribution.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 349-354
نویسندگان
, , ,