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.

Is there a way to (efficiently) enumerate all simple graphs with a given number of vertices up to isomorphism? That is, I don't care about the degeneracy of a graph, only the set of isomorphicly isomorphically unique ones of a given size.

share|improve this question
    
In a class I took last spring one of the term projects was on this, his final results are here wiki.ucfilespace.uc.edu/groups/combgen/wiki/972b8/… . –  JSchlather Dec 13 '10 at 18:29
1  
This is a difficult problem, which I am sure is exponentially difficult. For low numbers of vertices one can rely on various graph invariants, but in general this is quite complex. I've encountered this issue in calculating bases for "graph homology," but the number of isomorphism classes of graphs blows up quickly. –  Grumpy Parsnip Dec 13 '10 at 21:47
    
@Jacob: I like your output. It would be even nicer if you just kept the connected graphs, and tried to present the graphs planarly, if possible, or minimizing intersections! –  Mariano Suárez-Alvarez Jan 3 '11 at 3:32

1 Answer 1

up vote 2 down vote accepted

Since almost all graphs have a trivial automorphism group, there are asymptotically $2^{n \choose 2}/n!=O(2^{n^2})$ non-isomorphic graphs.

Suppose you could encode each graph using 1 bit (of course you can't actually do this, but this will help give a lower bound on the complexity). If the input string $n$ is encoded using $O(\log n)$ bits, then merely writing a "1" for each non-isomorphic graph would require at least double-exponential time $O(2^{(2^{\log n})^2})=O(2^{2^{2 \log n}})$.

On top of this, you want to return a string from which you can reconstruct the graph, and (possibly) require some form of isomorphism detection. All in all, this is not going to be easy (no matter how clever your algorithm is).

However, you might want to play around with geng, which comes with nauty, which can generate a list of such graphs. There's probably many other programs as well that I'm not familiar with.

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.