3
$\begingroup$

I am trying to enumerate all non-isomorphic graphs of size n and found this question: Enumerate all non-isomorphic graphs of a certain size

The accepted answer describes a method to do this:

Assume we know all non-isomorphic graphs of size n-1. Take each of them and add a new vertex in all possible ways. Then for all these graphs calculate a canonical labeling and check whether the new vertex has label 1 (or is in the same orbit of the automorphism group as the vertex with label 1). In that case, save the graph. Otherwise stop and try the next extension of the graph with n-1 vertices.

However, there's a problem: Say n=3 and we are currently considering the graph P2:

Now there are 4 ways to add a third vertex: enter image description here

However, two of them create the same graph, P3. Using a canonical labeling as explained above doesn't solve this issue. So the extensions themselves need to be canonical, somehow. I assume I need to use the automorphism group of the graph of size n-1 somehow.

So that's my question. How can I make sure that all my extensions give non-isomorphic graphs?

I know how to find canonical labelings and automorphism group generators, so your answer can use them as much as you like :)

Thanks!

Improve this question
$\endgroup$
7
  • $\begingroup$ "Then for all these graphs calculate a canonical labeling and check whether the new vertex has label 1." I'm not sure about the significance of the value '1' of the label (it seems important) or why exactly canonical labelling cannot be used to filter the isomorphic "duplicates"? (In other words I don't understand what's wrong with: 1. from n-1, try each new possible edge as you suggest; 2. canonically label results of 1 to find and remove isomorphic "duplicates".) $\endgroup$
    – badroit
    Commented Sep 14, 2015 at 15:41
  • $\begingroup$ Why don't you use existing software like nauty? $\endgroup$
    – Yuval Filmus
    Commented Sep 14, 2015 at 15:51
  • $\begingroup$ @badroit Any label from 1 to n would work. Also, how would filter the duplicates? I can't really keep a list of all graphs and check for isomorphisms. I'm pretty sure that that would use too much memory/time. Also the canonical forms of the two duplicate graphs might not be exaclty the same. It is only guaranteed that the canonical forms are isomorphic. (That's not the correct terminology I think. In other words the permutations of the labels to the labels of the canonical form might not be the same for the two cases. I hope that makes sense :P) $\endgroup$
    – Alex
    Commented Sep 14, 2015 at 15:52
  • $\begingroup$ @YuvalFilmus I need to understand the algorithm, because I want to apply it to a similar problem where I need to find graphs of a special type. I am already using bliss to find canonical labelings and automorphism group generators. $\endgroup$
    – Alex
    Commented Sep 14, 2015 at 15:54
  • $\begingroup$ @Alex, I am still confused. :) In your example, your two "duplicate" middle graphs are isomorphic. You can compute the canonical labelling for all four graphs, and from that (if worried about the memory for storing all graphs) compute a hash with sufficient length to avoid a collision. Prune graphs with a hash you've already seen as you go. If you are computing the canonical labelling of all graphs anyways, then afterwards computing a hash and using that to filter duplicates is relatively cheap. (The question after that is if there is a more efficient method!) $\endgroup$
    – badroit
    Commented Sep 14, 2015 at 17:02

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.