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
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.