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!

  • 1
    "So it is enough to find the number unlabeled graphs on$n$vertices." The words *non-isomorphic* and *unlabeled* mean the same thing.2012-01-19

1 Answers 1

5

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

  • 0
    Great m$i$nds think alike.2012-01-19