6
$\begingroup$

As my subject line asks, is there a formula for finding the number of nonisomorphic simple graphs there are with n nodes, outside of trial, error, and enumeration over max degrees of vertices?

Thanks in advance...

$\endgroup$
0

1 Answer 1

3
$\begingroup$

This is OEIS A000088. Two asymptotic formulas are given, the first of which is

$$a(n)=\frac{2^{\binom{n}2}}{n!}\left(1+\frac{n^2-n}{2^{n-1}}+\frac{8n!(3n-7)(3n-9)}{2^{2n}(n-4)!}\right)+O\left(\frac{n^5}{2^{5n/2}}\right)\;,$$

but there does not appear to be a nice closed form.

$\endgroup$
3
  • $\begingroup$ Thanks for the response... so for small values of n, drawing them seems to be the path of least resistance. $\endgroup$ Apr 7, 2013 at 17:44
  • $\begingroup$ @StatsViaCsh: You’re welcome. Or simply using the OEIS data for $n\le 19$. (And since that’s already $24637809253125004524383007491432768$, for any bigger $n$ an approximation might be adequate anyhow.) $\endgroup$ Apr 7, 2013 at 18:20
  • $\begingroup$ Actually the table goes up to $n=75$ in the b-file. These numbers must have been found by a non-constructive method of counting. I'm guessing Polya's Theorem; an implementation is discussed here. $\endgroup$ Apr 7, 2013 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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