# Efficiently generating all regular/bidegreed graphs

There is a related question on how to generate all regular graphs; however, the procedure is random and repeats the generated graphs. Plus, there is no stop condition, unless recording the total number of non-isomorphic graphs and matching it to the known numbers.

I wonder if there is a more efficient procedure that loops over all possible regular/bidegreed graphs? By more efficient, I mean return each regular graph only once, but if it's hard maybe other generation schemes that minimize the number of repetitions.

Ideally, I would like to have this procedure to generate all bidegreed graphs of order 20-30. But if bidegreed graphs are tough, at least for regular graphs.

By bidegreed graphs, I mean connected graphs that have only two possible values of degrees, $$a$$ and $$a+1$$, for any $$a \ge 2$$. The motivation for this is the reconstruction conjecture for this type of graphs.

• Welcome to Matheoverflow , Sergey ! Jan 5, 2021 at 8:03

You probably know that the number of regular graphs grows pretty quickly as n grows, so if you want to explicitly generate all 5-regulars on 20 vertices ($$4.22 \times 10^{15}$$ graphs by OEIS A165626), you are in for some serious computation no matter how efficient your method is. If you don't actually need to explicitly generate each graph, but do some related task (e.g. just count the graphs), you may find faster ways.
(Edited) For bidegreed graphs as per your definition, where the two degrees differ by one, geng will still work since you can specify minimum and maximum degree, e.g. generate graphs whose vertices have degrees in the interval $$[4,5]$$. For more general bidegreed graphs, where the two degrees are further apart (say, 3 and 6), I don't know of an existing tool but I guess similar algorithms will work, and you might be able to tweak the geng program for this.
• For regular graphs, nauty is outperformed by minibaum and genreg, see caagt.ugent.be/minibaum and sourceforge.net/projects/genreg . Those can't do non-regular, but nauty will do them. You won't be able to get to 20 vertices for $\{a,a+1\}$ though, except for $a=1,2,3$ with a lot of effort (too many graphs). Jan 5, 2021 at 12:10