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...
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Apr 6, 2013 at 21:25
-
$\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