Key points are not available for this paper at this time.
We estimate the minimum number of distance queries that is sufficient to reconstruct the binomial random graph G (n, p) with constant diameter with high probability. We get a tight (up to a constant factor) answer for all p>n^-1+o (1) outside "threshold windows" around n^-k/ (k+1) +o (1), k>₀: with high probability the query complexity equals (n^4-dp^2-d), where d is the diameter of the random graph. This demonstrates the following non-monotone behaviour: the query complexity jumps down at moments when the diameter gets larger; yet, between these moments the query complexity grows. We also show that there exists a non-adaptive algorithm that reconstructs the random graph with O (n^4-dp^2-d n) distance queries with high probability, and this is best possible.
Krivelevich et al. (Sun,) studied this question.