{
  "id": "1301.1097",
  "version": "v1",
  "published": "2013-01-07T02:25:32.000Z",
  "updated": "2013-01-07T02:25:32.000Z",
  "title": "Note on packing of edge-disjoint spanning trees in sparse random graphs",
  "authors": [
    "Xiaolin Chen",
    "Xueliang Li",
    "Huishu Lian"
  ],
  "comment": "9 pages",
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-01-07T02:25:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C05",
      "05C70",
      "05C80"
    ],
    "keywords": [
      "sparse random graphs",
      "minimum degree",
      "spanning tree packing number",
      "hitting time",
      "edge-disjoint spanning trees equals"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1301.1097C"
    }
  }
}