Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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": http://algo.inria.fr/flajolet/Publications/books.html

share|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 oeis.org/A204329 seems relevant. –  Robert Young Oct 12 '12 at 20:39

1 Answer 1

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 http://arxiv.org/abs/1204.4580 . I don't think there is much prospect of finding generating functions.

share|improve this answer

Your Answer

 
discard

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.