Multigraph enumeration with connection number limitation of nodes

Question

I need to generate multigraphs by several labeled nodes. Each node has a limitation of connection number, and they always higher or equal than 3.

For example:

{0: 3, 1: 3, 2: 4}

Nodes {0, 1} are adjacent with 3 edges respectively; node {2} is adjacent with 4 edges. The only one answer of the example is follow:

The result of the example

I'm now using NetworkX module of Python, it's using edge set as the expression of graphs. For the above image, it's expression is:

MutiGraph([(0, 1, 0), (0, 2, 0), (0, 2, 1), (1, 2, 0), (1, 2, 1)])

For more simpler, another expression implement on my Cython library is:

Graph([(0, 1), (0, 2), (0, 2), (1, 2), (1, 2)])

As a newcomer of Graph Enumeration Algorithm, I'm now using recursive method that has terrible performance. There needs some improvements for complexity, such like permutation or combination methods.

Update:

With the method of create Diophantine Equations like this (where $n_{ij} = n_{ji}$ is the number of edges $\{i, j\}$):

$$ n_{01} + n_{02} = 3 \\ n_{01} + n_{12} = 3 \\ n_{02} + n_{12} = 4 $$

I'm not sure how to transform the multivariate equation into Hermite normal form.

Number of variables is $\frac{n(n - 1)}{2}$. In the bigger case, like {0: 3, 1: 3, 2: 3, ..., 6: 3} has 15 variables but only 6 equations, it's matrix after doing Gaussian elimination will become:

[[ 1  0  0  0  0  0  0  0  0 -1 -1 -1 -1 -1 -1 -3]
 [ 0 -1  0  0  0  0  1  1  1  0  0  0  1  1  1  3]
 [ 0  0  1  0  0  0  1  0  0  1  0  0  1  1  0  3]
 [ 0  0  0  1  0  0  0  1  0  0  1  0  1  0  1  3]
 [ 0  0  0  0  1  0  0  0  1  0  0  1  0  1  1  3]
 [ 0  0  0  0  0  1  1  1  1  1  1  1  1  1  1  6]]

Answer 1

Since you have labeled vertices, this seems to me to more of a number theory problem than a graph theory problem. Let $n_{ij}=n_{ji}$ be the number of edges joining vertices and . Then the example problem is simply to find all solutions to $$\begin{align}n_{01}+n_{02}&=3\\n_{01}+n_{12}&=3\\n_{02}+n_{12}&=4\end{align}$$ in nonnegative integers.

If this is correct, look at "Algorithms for Hermite and Smith Normal Matrices and Linear Diophantine Equations," by Gordon H. Bradley, Math. Comp. vol. 25 Number 116 (October 1971)