Packing arborescences in random digraphs
Mar 25, 2019
Carlos Hoppen, Roberto F. Parente and Cristiane M. Sato
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 −1 i=0 ( − 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. Keywords: random graph, random digraph, edge-disjoint spanning tree, spanning tree, packing arborescence.
The whole paper is available here.
Share on Facebook
