How many N by N adjacency matrices exist with maximum degree of m

Question

I want to calculate the number of adjacency matrices corresponding to graphs with $N$ nodes satisfying all of the following properties:

1. There are no isolated nodes (each row of the matrix must have at least one 1).
2. The maximum degree for each node is at most $m \leq N$ (For example, if $m=3$, then each row of the matrix can have at most three 1s).
3. The adjacency matrix represents an undirected graph.

My attempts thus far: I know that the number of adjacency matrices for an undirected graph with $N$ nodes is $2^{N(N-1)/2}$, but I have not been able to incorporate the remaining assumptions.

Answer 1

This is an incomplete solution, and I would like to come back to this when I have time. Hopefully you can take this as a starting point and run with it. Note that if you just want an approximation, you can use the Monte Carlo method. Let me know if this interests you and I can expand.

Assumption. $0 \leq n \leq m < N$ are integers.

Let's start with a simple version of your problem in which we drop the requirement of undirectedness.

Let $g(i) \equiv {}_{N-1} C_i \cdot {}_2F_1(1, i - N + 1; i + 1; -1)$ where ${}_a C_b$ is the binomial coefficient and ${}_2F_1{}$ is the ordinary hypergeometric function.

Lemma (Counting digraphs). There are exactly $(g(n) - g(m+1))^N$ directed graphs with (i) $N$ nodes, (ii) $n \leq \operatorname{outdeg}(v) \leq m$, and (iii) no self-loops (i.e., no edges of the form $v \rightarrow v$).

By symmetry, the above also holds if we replace $\operatorname{outdeg}$ with $\operatorname{indeg}$.

Proof. There are ${}_{N-1} C_k$ ways to assign $k$ edges to a single node if we exclude self-loops. It follows that there are $\sum_{k = n}^m {}_{N-1} C_k = \sum_{k = 0}^m {}_{N-1} C_k - \sum_{k = 0}^{n-1} {}_{N-1} C_k$ ways to assign edges to a single node. Some tedious algebra reveals that $\sum_{k = 0}^{\ell-1} {}_{N-1} C_k = 2^{N-1} - g(\ell)$, from which the result follows.

Figure. $\log$ of the number of digraphs when $n = 0$ (values $m \geq N$ are capped to $N - 1$).

Let's return to your original problem. This problem is much harder because unlike the simpler problem above, one cannot "uncouple" the nodes of the graph to obtain an expression of the form $(\cdot)^N$.

Let $\mathbb{N}$ denote the nonnegative integers. When $k$ is a positive integer, let $\mathbb{N}^k$ denote the usual Cartesian product. For convenience, let $A^0 \equiv \{ 0 \}$ for any set $A$. Let $\mathbf{x}_{(-1)} \equiv (x_2, \ldots, x_N)$ denote the vector $\mathbf{x}$ with its first co-ordinate removed. When $\mathbf{x} \equiv (x_1)$ is a singleton vector, we interpret this as $\mathbf{x}_{(-1)} \equiv 0$.

Let $u_0(0) = 1$. For each positive integer $k \leq N$, let $u_k : \mathbb{N}^k \rightarrow \mathbb{N}$ by $$ u_k(\mathbf{x}) = \sum_{\mathbf{y} \in \mathcal{Y}} u_{k-1}(\mathbf{x}_{(-1)} + \mathbf{y}) \qquad \text{where} \qquad \mathcal{Y} \equiv \left \{ \mathbf{y} \in \{0,1\}^{k-1} \colon n \leq x_1 + \mathbf{1} \cdot \mathbf{y} \leq m \right \}. $$

Lemma (Counting undirected graphs). There are exactly $u_N(\mathbf{0})$ undirected graphs satisfying the same properties (i), (ii), and (iii) as above.

Code implementing the recurrence is given at the end of this post. Note, however, that this code only has a slight edge over the naive $O(2^{N^2})$ algorithm involving enumerating all possibilities.

Figure. $\log$ of the number of undirected graphs when $n = 0$.

import itertools
import numpy as np

_cache = {}

def log_num_undirected_graphs(num_nodes, min_out_degree, max_out_degree):

    def u(x):
        k = len(x)
        if k == 0: return 1
        key = (min_out_degree, max_out_degree) + x
        result = _cache.get(key, None)
        if result is not None: return result
        result = 0
        Y = itertools.product((0, 1), repeat=k-1) if k > 1 else [()]
        for y in Y:
            tmp = x[0] + sum(y)
            if tmp < min_out_degree or tmp > max_out_degree: continue
            x_prime = tuple(x_i + y_i for x_i, y_i in zip(x[1:], y))
            result += u(x_prime)
        _cache[key] = result
        return result

    zero = (0,) * num_nodes
    return np.log(u(zero))