Shortest-weight paths in random regular graphs

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\ge 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}$.

20 pages. arXiv admin note: text overlap with arXiv:1112.6330