pith. sign in

arxiv: 1301.1097 · v1 · pith:EOMV6M5Cnew · submitted 2013-01-07 · 🧮 math.CO

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

classification 🧮 math.CO
keywords spanningdegreegraphminimumnumberpackingrandomalmost
0
0 comments X
read the original abstract

The \emph{spanning tree packing number} of a graph $G$ is the maximum number of edge-disjoint spanning trees contained in $G$. Let $k\geq 1$ 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 $(\log n+\omega(1))/n\leq p\leq (1.1\log n)/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 $p\geq (51\log n)/n$, almost surely the random graph $G(n,p)$ satisfies that the spanning tree packing number is less than the minimum degree.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.