Shortest-Weight Paths In Random Regular Graphs

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 α^logn edges where α^ is the unique solution of the equation αlog(d−2d−1α)−α=d−3d−2, for α>d−1d−2.