I have been trying to count the number of graphs up to isomorphism which are:
- Simple
- Connected
- 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) = \sum_{i=x}^y t(i) \cdot \binom{a(i)} { n – i – 1}$$
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) = \sum_{k-1}^i (i – k),
\qquad y = n+1,\quad\text{and}$$
$x \geq $
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 trees including isomorphism with $i$ vertices is $i^{i-2}$,
and have placed that as the upper bound for $t(i)$.
And that [according to Wikipedia] there is an estimate for the number of such trees up to isomorphism:
$t(i)\sim C \alpha^i i^{-5/2}$
with $C=0.534949606…$ and $\alpha=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.
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.
Best Answer
Start here and you might find more.
http://oeis.org/A002905