3
$\begingroup$

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.

$\endgroup$

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.