The flooding time in random graphs (Q1424670)

Asymptotics of the flooding time \(T_n(p)\) (i.e. a time of first-passage percolation) in a random graph \(G_p(N)\) is considered. The graph \(G_p(N)\) has \(N\) nodes and each pair of nodes is connected by a link with probability \(p=p_N\) independently from others. The links are weighted by exponentially distributed random variables with mean 1. (The weight of a link is the time needed to pass through the link.) It is shown that if \(Np_N/(\log N)^3\to\infty\) as \(N\to\infty\), then \[ \lim_{N\to\infty}\Pr\{Np_N T_N(p_N)-2\log N< z\}=\Lambda^{(2*)}(z), \] where \(\Lambda^{(2*)}\) denotes the two-fold convolution of the Gumbel distribution function \(\Lambda\).