Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm wondering whether I could determine the expected value for the diameter of a random graph given the distribution of the degree of the vertices.

Specifically I have a network of computers that open random connections to each other. I know that each computer attempts to keep a minimum size $k$ connection pool open at all times, but it may also receive incoming connections. The connection graph therefore is not $k$-regular. I'd like to know what the expected diameter of that network would be.

share|improve this question
One would need a reason to suspect that the distribution of the degree of the vertices determines the diameter. This does not seeem to be the case. –  Did Feb 1 '13 at 15:40
I don't see what else could be relevant to determining the diameter. Assuming that edges in the graph are chosen uniformly at random that is. –  cdecker Feb 1 '13 at 19:36
The reader is in need of some explanations about the model you have in mind. Do you decide randomly that each edge is present or not, independently of the others? Then you cannot choose the distribution of the degrees... –  Did Feb 1 '13 at 19:44
add comment

1 Answer

Does the paper "Chung, Fan, and Linyuan Lu. The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences 99.25 (2002): 15879-15882." answer your question? This can be downloaded here.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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