Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
1  
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. – Grumpy Parsnip Jan 19 '12 at 20:22
    
"So it is enough to find the number unlabeled graphs on n vertices." The words non-isomorphic and unlabeled mean the same thing. – Austin Mohr Jan 19 '12 at 21:34

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

share|cite|improve this answer
    
Great minds think alike. – Grumpy Parsnip Jan 19 '12 at 21:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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