MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there some known sequence which gives me the number of graphs with diameter d?

Similarly is there some 2D-sequence which gives me the number of graphs with n vertices and diameter d?

If there is no closed form is there some way to study this problem in terms of generating function and apply to it some asymptotic analysis like in "Analytic Combinatorics":

share|cite|improve this question
There are infinitely many graphs with diameter 2 -- take a n-pointed star for any n. I usually try to find results like this by calculating the first couple terms of the sequence and then searching the Online Encyclopedia of Integer Sequences. I wasn't able to find an answer to your exact question, but the sequence seems relevant. – Robert Young Oct 12 '12 at 20:39
up vote 2 down vote accepted

The asymptotic number of graphs with given order and diameter was determined recently by Zoltán Füredi and Younjin Kim, see . I don't think there is much prospect of finding generating functions.

share|cite|improve this answer

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.