Enumerating Counts Using Self-Testing

Question

Brendan Mackay has already done the work of finding all non-isomorphic graphs of n variables that can be found here (in simple graphs): http://cs.anu.edu.au/~bdm/data/graphs.html

I believe this was done using polya enumeration, which I understand the basics. I would like to expand on this and allow the auto saws on these graphs. So, I would like to find all non-morphic graphs of n variables, including self loops. This will be directly used for another part of my code and provide mass optimization. I'm just not quite sure how to do this.

To be clear, Brendan Mackay files give all non-isomorphic graphs, i.e. in the edge notation,

1-2 1-3

is a graph with an edge between vertices 1 and 2 and 1 and 3. I want this list to also include self loops, i.e.

1-2 1-3 1-1

or

1-2 1-3 1-1 2-2

I want a minimum number of graphs, so all are non-isomorphic. How can I find them, hopefully using the data that Brendan Mackay is available for simple graphs?

Answer 1

First of all, you should notice that if two graphs are not isomorphic, then these graphs with some additional autoliths are not isomorphic.

If you need it during programming, and the size of the graphs is small, I would generate for each non-isograph all possible graphical diagrams of the cycle.

The simplest thing is to add an additional node, and each node with a self loop will be associated with this node. (instead of having a loop). Using nauty, you can check if any two are isomorphic. You can speed things up further if you notice that if two iso-encoded versions are loop-encoded, then they must have the same number of connections with a special node.