Shortest-Weight Paths In Random Regular Graphs

Consider a random regular graph with degree d and of size n. Assign to each edge an independent and identically distributed 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 (alpha) over cap log n edges, where (alpha) over cap is the unique solution of the equation alpha log (d-2/d-1 alpha) -alpha = d-3/d-2 for alpha > d-1/d-2.


Published in:
Siam Journal On Discrete Mathematics, 28, 2, 656-672
Year:
2014
Publisher:
Philadelphia, Siam Publications
ISSN:
0895-4801
Keywords:
Laboratories:




 Record created 2014-08-29, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)