[Math] Number of graphs with $n$ edges

co.combinatoricsgraph theory

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) = \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

Related Question