2012/10/09 by Hamed Amini, Yuval Peres, Amini, Hamed +1
Computer Science · Mathematics · #05C80 #60C05 #90B15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #math.CO #math.PR #msc:05C80 #msc:60C05 #msc:90B15
paper · pdf · doi:10.48550/arxiv.1210.2657
20 pages. arXiv admin note: text overlap with arXiv:1112.6330
arxiv created 2012/10/09 · openalex publication_date 2012/10/09 · arxiv updated 2012/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ≥ 3, we show that the longest of these shortest-weight paths has about αlog n edges where α is the unique solution of the equation αlog((d-2)/(d-1)α) - α= (d-3)/(d-2), for α> (d-1)/(d-2).