Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges

Question

Let $G( n, m )$ be the set of all possible connected graphs of $n$ nodes and $m$ edges such that, for each $g_1 \in G( n, m )$, $g_2 \in G( n, m )$, if $g_1 \neq g_2$ then $g_1$ and $g_2$ are non-isomorphic.

Question

How large can $|G( n, m )|$ be? Is it polynomial in both $n$ and $m$? Or is it superpolynomial in either $n$ or $m$?

Answer 1

According to Bollobas (Random Graphs), if you make "natural assumptions" on $n$ and $m$ there are $n!$ times more labelled graphs on $n$ vertices and $m$ edges than random unlabelled graphs on $n$ vertices and $m$ edges, so roughly $\frac{1}{n!}{{n \choose 2} \choose m}$ unlabelled graphs on $n$ vertices and $m$ edges. If you pick something like $m = \frac{1}{2}{n \choose 2}$, all those graphs should be connected with high probability, so I'd say --> massively superpolynomial !

Of course, you can break those "natural assumptions" by setting $m = 0$, or $m<n-1$ in your case...

Nathann

Answer 2

See OEIS sequence A054924 for discussion and references.

As far as I know this grows faster than any polynomial. In particular, see the sequence of the largest value of |G(n,m)| for each $n$.