Packing arborescences in random digraphs

DOI10.1016/J.ENDM.2017.07.015MaRDI QIDQ1689982zbMATH OpenOpenAlexFDO

Authors Carlos Hoppen, R. F. Parente, Cristiane M. Sato

Publication date 18 January 2018

Full work available at URL https://arxiv.org/abs/1605.05764

zbMATH Keywords

random graphspanning treerandom digraphedge disjoint spanning treepacking arborescence

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the problem of packing arborescences in the random digraph $mathcalD(n,p)$, where each possible arc is included uniformly at random with probability $p=p(n)$. Let $lambda(mathcalD(n,p))$ denote the largest integer $lambdageq0$ such that, for all $0leqellleqlambda$, we have $su{m}_{i=0}^{ell-1}(ell-i)|v:d^{in}(v)=i|leqell$. We show that the maximum number of arc-disjoint arborescences in $mathcalD(n,p)$ is $lambda(mathcalD(n,p))$ a.a.s. We also give tight estimates for $lambda(mathcalD(n,p))$ depending on the range of $p$.

Recommendations

• Packing arborescences in random digraphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Arboricity and spanning‐tree packing in random graphs
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs

Cites work

• scientific article; zbMATH DE number 3659627 (Why is no real title available?)
• A Reduction Method for Edge-Connectivity in Graphs
• Arboricity and spanning-tree packing in random graphs with an application to load balancing
• Combinatorial optimization. Packing and covering
• Edge-Disjoint Spanning Trees of Finite Graphs
• Edge-disjoint Hamilton cycles in random graphs
• Hamilton decompositions of regular expanders: applications
• On the Problem of Decomposing a Graph into n Connected Factors
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• Rainbow arborescence in random digraphs
• Robust Hamiltonicity of random directed graphs: extended abstract

Cited in

(5)

• Packing trees of unbounded degrees in random graphs
• Rainbow arborescence in random digraphs
• Packing tree factors in random and pseudo-random graphs
• Packing arborescences in random digraphs
• Arboricity and spanning‐tree packing in random graphs

This page was built for publication: Packing arborescences in random digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1689982)