Multitrees in random graphs

DOI10.37236/10804arXiv2110.08876MaRDI QIDQ6380581FDOQ6380581

Authors: Alan Frieze, Wesley Pegden 

Publication date: 17 October 2021

Abstract: Let $$ and $sgeq2$. Let $e_{i,j},,i=1,2,ldots,N,,j=1,2,ldots,s$ be $s$ independent permutations of the edges $E(K_n)$ of the complete graph $K_n$. A {em MultiTree} is a set $Isubseteq[N]$ such that the edge sets $E_{I,j}$ induce spanning trees for $j=1,2,ldots,s$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $O(nlogn)$ bound for $sgeq3$.

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

This page was built for publication: Multitrees in random graphs

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