I'm looking to generate all regular multi-graphs over $n$ vertexes and of degree $d$ in mathematica (side note: $n,d$ are fairly small, this problem gets unmanagable very fast). So here $n,d$ are my input. The way I approached this problem was as follows:

n = 8;
d = 6;

(*Enteries of a Generic Strictly Upper-Triangular Matrix*)
M = UpperTriangularize[Array[m, {n, n}], 1];
mvar = Flatten[Table[m[i, j], {i, n}, {j, i + 1, n}]];

(*Condition I: Entries are non-negative*)
NNFunc[0] = True;
NNFunc[i_] := mvar[[i]] >= 0 && NNFunc[i - 1];
NNCdt = NNFunc[Length[mvar]];

(*Condition II: Sum of kth Row + kth Column = d*)
RpC = Total[M, {2}] + Total[M, {1}];
RpCFunc[0] = True;
RpCFunc[i_] := (RpC[[i]] == d) && RpCFunc[i - 1];
RpCCdt = RpCFunc[n];

(*Final Condition*)
CdtFin = RpCCdt && NNCdt;

(*Now we Solve This System of Equations*)
sol = Solve[CdtFin, mvar, Integers]

This code basically works on the fact that a graph is $d$-regular if and only if the sum of each row (or column) of its adjacency matrix (which is symmetric) is equal to $d$. I have turned this into a set of equations determined by RpCCdt above. Also one needs to make sure to find solutions with non-negative integers, this is implemented in NNCdt.

This code works quite nicely and fast until certain point! The numbers $n=8, d=6$ as I gave are more or less the threshold beyond which mathematica goes into oblivion! At first I thought maybe finding the solutions beyond certain point is hard, but no! I changed the Solve command into FindInstance command and mathematica struggles even in finding 10 solutions! There are way more trivial solutions than 10 that mathematica should not even break a sweat in finding them.

I think it is because beyond certain number of conditions the Solve and/or FindInstance encounter issues (the only explanation I came up with). Does anybody has a solution or a way around this issue?

If anyone has a better solution for generating all $d$-regular graphs over $n$ vertexes, that'd be great; by the way what I really care about is just a single graph from each isomorphism class (it doesn't show here, but in another part of the code I had taken care of that). Or if there is a way to fix this issue, but keep my code, again great.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.