Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777129 | Electronic Notes in Discrete Mathematics | 2017 | 7 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Carlos Hoppen, Roberto F. Parente, Cristiane M. Sato,