(Efficiently) Generating graphs with vertex degree 3 for all vertices

Question

I'm working on a graph theory problem, and given $n$ vertices, I would like to be able to generate all non-isomorphic connected graphs (not necessarily simple) with $n$ vertices, each having degree 3. Currently I'm doing the graph finding in Sage, but the included graph packages have given me problems, so I've used dictionaries instead. My approach is to generate graphs with vertex degree at most three, and recurse on previous such lists, increasing edge number by 1 each time. This is not optimal, and is really time-intensive, mostly because of my primitive isomorphism-checking function.

So, I would like to know if it is possible to generate this type of list (connected graphs with maximal degree at most 3) in Mathematica, because I can actually plot them there easily as well. I've been using a converter (line 46 here) that gives the Mathematica command to plot the graphs from Sage, for example,

{GraphPlot[{1 -> 2, 1 -> 1, 2 -> 3, 2 -> 3}], 
 GraphPlot[{1 -> 2, 1 -> 1, 2 -> 3, 2 -> 4}], 
 GraphPlot[{1 -> 2, 1 -> 1, 2 -> 3, 3 -> 3}], 
 GraphPlot[{1 -> 2, 1 -> 1, 2 -> 3, 3 -> 4}], 
 GraphPlot[{1 -> 2, 1 -> 2, 1 -> 3, 2 -> 3}], 
 GraphPlot[{1 -> 2, 1 -> 2, 1 -> 3, 2 -> 4}], 
 GraphPlot[{1 -> 2, 1 -> 2, 1 -> 3, 3 -> 4}], 
 GraphPlot[{1 -> 2, 1 -> 3, 1 -> 4, 2 -> 3}], 
 GraphPlot[{1 -> 2, 1 -> 3, 1 -> 4, 2 -> 5}], 
 GraphPlot[{1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4}], 
 GraphPlot[{1 -> 2, 1 -> 3, 2 -> 4, 3 -> 5}]}

gives all the graphs with 4 edges and vertices of degree at most 3. Any help in this regard would be appreciated. For the past two hours Sage has been computing all such graphs with 5 edges, and I would like at least 9-edge graphs, so things are not looking hopeful in that direction.

Maybe there are nice packages to do this with? I've looked at Combinatorica, but the graph-manipulating functions don't seem well-suited to my needs, though that is from a cursory inspection.

Answer 1

This might get you started. It generates (I think) all graphs of given number of vertices and degree, with the following caveats:

• They are undirected.
• They do not have self edges.
• Edges only have weight 1 (that is, no duplicated edges).

You might be able to modify to add those features.

Also this makes no attempt to weed out isomorphic graphs.

stepJ[j_, n_, deg_, partial_] := Module[
  {tally, needs, possibles, edges},
  tally = ConstantArray[0, n];
  Map[tally[[#]] += 1 &, Flatten[partial]];
  needs = deg - tally[[j]];
  If[needs == 0, Return[{partial}]];
  If[n - j < needs, Return[{}]];
  possibles = Subsets[Range[j + 1, n], {needs}];
  res = Reap[Do[
      edges = possibles[[k]];
      If[And @@ Thread[tally[[edges]] < deg],
       Sow[Join[partial, Thread[{j, edges}]]]]
      , {k, Length[possibles]}]][[2]];
  If[res === {}, {}, res[[1]]]
  ]

makeGraphs[vert_, deg_] := Module[
  {subgraphs, newpartials},
  subgraphs = stepJ[1, vert, deg, {}];
  Do[
   subgraphs = Flatten[Reap[
       Do[newpartials = stepJ[j, vert, deg, subgraphs[[k]]];
        If[newpartials =!= {}, Sow[newpartials]];
        , {k, Length[subgraphs]}]][[2]], 2], {j, 2, vert}];
  subgraphs
  ]

In[227]:= Timing[res = makeGraphs[8, 3];]

(*Out[227]= {11.560000, Null}*)

In[228]:= Length[res]

(*Out[228]= 19355*)