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\geq 3\), we show that the longest of these shortest-weight paths has about \({\alpha }_^logn\) edges where \({\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}\).