Shortest-Weight Paths in Random Regular Graphs

DOI10.1137/120899534zbMATH Open1303.05174arXiv1210.2657OpenAlexW1996534617MaRDI QIDQ3192154FDOQ3192154

Yuval Peres, Hamed Amini

Publication date: 26 September 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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 $dgeq3$, we show that the longest of these shortest-weight paths has about $hatalphalogn$ edges where $hatalpha$ is the unique solution of the equation $alphalog(fracd-2d-1alpha)-alpha=fracd-3d-2$, for $alpha>fracd-1d-2$.

Full work available at URL: https://arxiv.org/abs/1210.2657

zbMATH Keywords

shortest pathsfirst passage percolationlaw of large numbersrandom regular graphsweighted random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Stochastic network models in operations research (90B15)

Cited In (7)

• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• The diameter of weighted random graphs
• The shortest-path problem for graphs with random arc-lengths
• The Distribution of Path Lengths On Directed Weighted Graphs
• Diameter of the Stochastic Mean-Field Model of Distance
• Successive shortest paths in complete graphs with random edge weights

This page was built for publication: Shortest-Weight Paths in Random Regular Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192154)