3
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Welcome to Matheoverflow , Sergey ! $\endgroup$
    – Alexander Chervov
    Commented Jan 5, 2021 at 8:03

2 Answers 2

Reset to default
4
$\begingroup$

For regular graphs, one of the standard tools would be geng, a C program from the Nauty package. Source code is included so you can inspect the algorithm. It is pretty efficient, for example all 5-regulars on 12 vertices (7849 graphs) are listed in one second on a desktop PC. For the special case of 4-regulars there is genquarticg which is even faster.

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.

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ 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). $\endgroup$
    – Brendan McKay
    Commented Jan 5, 2021 at 12:10
4
$\begingroup$

Kim et al. in this paper proposed a construction method (not based on swaps) to build all simple graphs realizing a given degree sequence. It should work with regular or bidegreed graphs too.

I don't know if any implementation of this algorithm is available, but if you find or do such an implementation, I would be interested to know about its practical efficiency.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .