Note on packing of edge-disjoint spanning trees in sparse random graphs

arXiv1301.1097MaRDI QIDQ6238541FDOQ6238541

Huishu Lian, Xiaolin Chen, Xueliang Li

Publication date: 6 January 2013

Abstract: The emph{spanning tree packing number} of a graph $G$ is the maximum number of edge-disjoint spanning trees contained in $G$. Let $kgeq1$ be a fixed integer. Palmer and Spencer proved that in almost every random graph process, the hitting time for having $k$ edge-disjoint spanning trees equals the hitting time for having minimum degree $k$. In this paper, we prove that for any $p$ such that $(logn+omega(1))/nleqpleq(1.1logn)/n$, almost surely the random graph $G(n,p)$ satisfies that the spanning tree packing number is equal to the minimum degree. Note that this bound for $p$ will allow the minimum degree to be a function of $n$, and in this sense we improve the result of Palmer and Spencer. Moreover, we also obtain that for any $p$ such that $pgeq(51logn)/n$, almost surely the random graph $G(n,p)$ satisfies that the spanning tree packing number is less than the minimum degree.

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

This page was built for publication: Note on packing of edge-disjoint spanning trees in sparse random graphs

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