{
  "id": "1210.2657",
  "version": "v1",
  "published": "2012-10-09T16:26:25.000Z",
  "updated": "2012-10-09T16:26:25.000Z",
  "title": "Shortest-weight paths in random regular graphs",
  "authors": [
    "Hamed Amini",
    "Yuval Peres"
  ],
  "comment": "20 pages. arXiv admin note: text overlap with arXiv:1112.6330",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Consider a random regular graph with degree $d$ and of size $n$. Assign to each edge an i.i.d. exponential random variable with mean one. In this paper we establish a precise asymptotic expression for the maximum number of edges on the shortest-weight paths between a fixed vertex and all the other vertices, as well as between any pair of vertices. Namely, for any fixed $d \\geq 3$, we show that the longest of these shortest-weight paths has about $\\hat{\\alpha}\\log n$ edges where $\\hat{\\alpha}$ is the unique solution of the equation $\\alpha \\log(\\frac{d-2}{d-1}\\alpha) - \\alpha = \\frac{d-3}{d-2}$, for $\\alpha > \\frac{d-1}{d-2}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-10-09T16:26:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05C80",
      "90B15"
    ],
    "keywords": [
      "random regular graph",
      "shortest-weight paths",
      "precise asymptotic expression",
      "maximum number",
      "unique solution"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1210.2657A"
    }
  }
}