0
$\begingroup$

This question is similar to this question I asked earlier. In this question, however, I would like to know if there is a way to determine the expected diameter of a undirected unweighted graph given the number of nodes, $V$, and the number of edges, $E$?

$\endgroup$
1
$\begingroup$

Although the two questions sounds similar, it is completely different because we have a pretty good idea of what is a typical random graph -whereas in the other question, you must consider all graphs, the 'interesting' graphs will be dwarfed in number by the typical ones. The uniform random graph conditioned on having $n$ vertices and $m$ edges is called the Erdős–Rényi model, and often written $G(n,m)$. It is closely related to its binomial counterpart $G(n,p)$, where each edge is present with probability $p(n)$, and results can be transferred from one model to the other with some care.

Now back to the expected diameter, obviously the results differ wildly depending on the value of $m(n)$/$p(n)$, but there are pretty good bounds holding with high probability that are known. You should know where to look for with that information.

$\endgroup$
  • $\begingroup$ To the interested reader: Here is a paper by Fan Chung and Linyuan Lu which surveys results on likely diameter for $G(n,p)$ for various ranges of $p$. It is also has a nice table of how concentrated the likely diameter is. Some of the results for $np=c$ for $c$ close to 1 have been improved since then. $\endgroup$ – D Poole Sep 12 '16 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.