کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777129 1632570 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Packing arborescences in random digraphs
ترجمه فارسی عنوان
بسته بندی های مصنوعی در گرافیک های تصادفی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

We study the problem of packing arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p=p(n). Let λ(D(n,p)) denote the largest integer λ≥0 such that, for all 0≤ℓ≤λ, we have ∑i=0ℓ−1(ℓ−i)|{v:din(v)=i}|≤ℓ. We show that the maximum number of arc-disjoint arborescences in D(n,p) is λ(D(n,p)) a.a.s. We also give tight estimates for λ(D(n,p)) depending on the range of p.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 615-621
نویسندگان
, , ,