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
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:
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
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 :)
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$