Take the 2-minute tour ×
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.

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|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

2 Answers 2

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

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

For 1, you could use the Lemma that is not Burnside's.

share|improve this answer
    
You should add this as a comment, as it does not quite answer the question! –  Mariano Suárez-Alvarez Jan 19 '12 at 20:21
    
@DanielPietrobon: Is there a more elementary way? –  passenger Jan 19 '12 at 20:22
    
Dear passenger, Burnside's lemma is a little (but important) part in the solution of this problem. This is a classical, very difficult problem, and there is not much to hope for an "elementary way". –  Mariano Suárez-Alvarez Jan 19 '12 at 20:25

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.