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.

I'd love your help with this question.

Let $n\geq3$ be a fixed integer. How many non-isomorphic graphs with $V$ vertices and $E$ edges are there where $V+E=n$?

Thank you very much.

share|improve this question
1  
Do you have any reason to think there will be any kind of useful formula for this? –  Gerry Myerson Jun 17 '11 at 0:55
    
This is very hard for fixed $p$ and $q$, and $n$ isn't a particularly natural parameter here. –  Qiaochu Yuan Jun 17 '11 at 0:56
8  
For what it's worth, this is tabulated at oeis.org/A120412 –  Gerry Myerson Jun 17 '11 at 1:00
2  
FWIW, this was also posted at mathoverflow.net/questions/68017/counting-graphs –  JavaMan Jun 17 '11 at 2:29
    
Might a starting point be to think about how many planar connected graphs there which obey this condition? –  Joseph Malkevitch Sep 1 '11 at 21:05

1 Answer 1

This type of enumeration can be achieved using Polya Theory to attain a generating function. The best reference is Riordan, http://books.google.com/books?id=zWgIPlds29UC&lpg=PP1&pg=PP1#v=onepage&q&f=false, page 129. See page 143 for the application to counting graphs by |E| and |V|.

If would like to construct such graphs , there is a C program "nauty" developed by Brendan D. McKay, based on his math article http://cs.anu.edu.au/~bdm/nauty/pgi.pdf.

share|improve this answer

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.