Welcome to MathOverflow

Question

0

1

I have been trying to count the number of graphs up to isomorphism which are: 1. Simple 2. Connected 3. Have n-edges

I apologize in advance if there is ample documentation on this question, however, I have found none.

Thus far, my best overestimate is:

g(n) = The sum (t(i) * (a(i) choose (n - i - 1))) from i=x to y

where:

g(n) := the number of such graphs with n-edges t(i) := the number of trees up to isomorphism on i vertices a(i) := the number of non-adjacent vertices in a tree on i vertices

I have conjectured that: a(i) = the sum (i - k) from k=1 to i

y = n+1

x is greater than or equal to the number of vertices in the complete graph with the closest number of edges to n, rounded down

I have also read:

that the number of complete graphs including isomorphism with i vertices is i^(i-2), and have placed that as the upper bound for t(i)

And that there is an estimate for the number of such graphs up to isomorphism: c*(a^i)*(i^(-5/2)) with c=.534949606... and a=2.99557658565...

What I would like to know is: A. Is there an answer already found for this question? B. Is there any information off the top of your head which might assist me? C. Is this problem incredibly hard?

Again, I apologize if this is not appropriate for this site, and for the lack of TeX.

I am a sophomore undergraduate student, and I have been trying to answer or estimate this question for use as an upper bound for another larger question that I am working on.

Thanks for the help.

flag	asked Jun 3 2011 at 21:36 malloc8 1

Get the first few values, then look 'em up at the Online Encyclopedia of Integer Sequences. – Gerry Myerson Jun 3 2011 at 22:28

A. I doubt an exact number is known but I am pretty sure the question has been asked before and there is a lot of literature; B the rough order is $e^{n\log n}$ (give or take a constant factor in the exponent). C. That depends on the precision you want. The crude estimate I quoted is trivial but the more accurate bounds you want, the harder it gets. – fedja Jun 3 2011 at 23:12

1

It is certainly not the state of the art but a quick literature search yields the asymptotics $\left[\frac 2e\frac n{\log^2 n}\gamma(n)\right]^n$ with $\gamma(n)=1+c(n)\frac{\log\log n}{\log n}$ and $c(n)$ eventually between $2$ and $4$. Is it good enough for your purposes? – fedja Jun 4 2011 at 0:28

Thanks for your help. This will be enough to place an upper bound on what I was looking for, though I'm afraid I vastly underestimated the order of magnitude. Because of this, I doubt I'll be able to use this to produce a close estimate. For anyone interested in further pursuing this problem on it's own. If there is an estimate available for the average number of spanning trees in an n-vertex simple graph, I believe dividing the sum that I proposed: g(n) = The sum (t(i) * (a(i) choose (n - i - 1))) from i=x to y by a manipulation of this number may provide an estimate. – malloc8 Jun 4 2011 at 1:03

gordon-royle · Answer 1 · 2011-06-04 00:00:59Z UTC

2

Start here and you might find more.

http://oeis.org/A002905

answered Jun 4 2011 at 0:00

gordon-royle
2,687●9●20

Thanks, that was helpful. – malloc8 Jun 4 2011 at 1:04

Number of graphs with n-edges

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.