Welcome to MathOverflow

Question

3

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

flag	asked Oct 12 at 19:19 nomatter 55●3

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 at 20:39

Brendan McKay · Accepted Answer · 2012-10-12 23:32:13Z UTC

2

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.

answered Oct 12 at 23:32

Brendan McKay
9,120●1●13●33

Counting graphs with diameter d

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.