4
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Robert Young
    Oct 12, 2012 at 20:39

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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