How can I generate all non-isomorphic not-only-simple connected graphs with some restrictions?

Question

As the title says, I'd like to generate all non-isomorphic connected undirected graphs with specified numbers of vertices and edges. Also, I'd like to make the restriction to the degree of all vertices in the graph as $3 \le d(v_i) \le 4$.

Notice: I have no restriction for simple graph, so multi-edges and self-loops should be included, too!

It seems that the simple case could be generated by the program named nauty. I have no idea that if it works for generated all graphs or not.

Answer 1

You can do this with nAUTy, or more exactly with a pair of tools in the suite : geng and multig. For example, the following geng command:

geng -c 4 > simple.g6

gives all connected simple graphs on 4 vertices. This can then be passed to multig like:

multig -u -D4 simple.g6

I'm using the -u flag here to just count them and the -D flag to restrict the maximum degree to 4. If you remove the -u flag, and write to a file, you can then use showg to convert the g6 format graphs into a more readable format.

There does not seem to be a minimum degree option, so you might have to use pickg to do this. With all these tools, there should be instructions in the manual, or use the -help flag.