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

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.

share|improve this question
    
Get the first few values, then look 'em up at the Online Encyclopedia of Integer Sequences. –  Gerry Myerson Jun 3 '11 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 '11 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 '11 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 '11 at 1:03
add comment

1 Answer

Start here and you might find more.

http://oeis.org/A002905

share|improve this answer
    
Thanks, that was helpful. –  malloc8 Jun 4 '11 at 1:04
add comment

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.