Consider a random regular graph with degree $d$ and of size $n$. Assign toeach edge an i.i.d. exponential random variable with mean one. In this paper weestablish a precise asymptotic expression for the maximum number of edges onthe shortest-weight paths between a fixed vertex and all the other vertices, aswell as between any pair of vertices. Namely, for any fixed $d geq 3$, we showthat the longest of these shortest-weight paths has about $hat{lpha}log n$edges where $hat{lpha}$ is the unique solution of the equation $lphalog(rac{d-2}{d-1}lpha) - lpha = rac{d-3}{d-2}$, for $lpha >rac{d-1}{d-2}$.
展开▼
机译：考虑一个随机正则图，其度数为$ d $，大小为$ n $。为每个边缘分配一个i.d.平均值为1的指数随机变量。在本文中，我们为固定顶点和所有其他顶点之间以及任何一对顶点之间的最短权重路径上的最大边数建立了精确的渐近表达式。也就是说，对于任何固定的$ d geq 3 $，我们证明这些最短权重路径中的最长路径大约有$ hat { alpha} log n $ edges，其中$ hat { alpha} $是方程$ alpha log（ frac {d-2} {d-1} alpha）- alpha = frac {d-3} {d-2} $，对于$ alpha> frac {d -1} {d-2} $。
展开▼
