5
$\begingroup$

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$?

$\endgroup$

2 Answers 2

8
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.