4
$\begingroup$

In the following the graphs are assumed to be undirected and simple.

1.Enumerate the number of non-isomorphic graphs on $n$ vetrices where $n$ is fixed.

Here are some ideas I had:

The number of labeled graphs is $ 2^{\frac{n(n-1)}{2}} $.

So it is enough to find the number unlabeled graphs on $n$ vertices.I have no idea for this.

2.Enumerate the number of non-isomorphic graphs on $n$ vertices and $m$ edges where $n,m$ are fixed.

Can we find a closed formula for each of this?

Any help?

Thank you!

$\endgroup$
  • 2
    $\begingroup$ This is a rather difficult problem. See Sloane's oeis.org/A000088 which gives the number of graphs on $n$ vertices, and has many references. $\endgroup$ – Cheerful Parsnip Jan 19 '12 at 20:22
  • 1
    $\begingroup$ "So it is enough to find the number unlabeled graphs on n vertices." The words non-isomorphic and unlabeled mean the same thing. $\endgroup$ – Austin Mohr Jan 19 '12 at 21:34
5
$\begingroup$

See e.g. https://oeis.org/A000088 and references given there.

$\endgroup$
  • $\begingroup$ Great minds think alike. $\endgroup$ – Cheerful Parsnip Jan 19 '12 at 21:35

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.