Packing arborescences in random digraphs

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.

NeuroCineMat
Featuring this week:
Newsletter

Stay informed on our latest news!



Previous issues

NeuroMat Brachial Plexus Injury Initiative
Logo of the NeuroMat Brachial Plexus Injury Initiative
Neuroscience Experiments System
Logo of the Neuroscience Experiments System
NeuroMat Parkinson Network
Logo of the NeuroMat Parkinson Network
NeuroMat's scientific-dissemination blog
Logo of the NeuroMat's scientific-dissemination blog