Counts of regular multigraphs

This page is an appendix to the paper Asymptotic enumeration of symmetric integer matrices with uniform row sum, by Brendan D. McKay and Jeanette C. McLeod, arXiv:1108.4496v1.

Define M(n,k) to be the number of loop-free multigraphs which have n vertices and are regular of degree k.

Equivalently, M(n,k) is the number of n-by-n symmetric nonnegative integer matrices with zero diagonal and all row sums equal to k.

The Maple file symmint.maple defines a function M(n,k) which can compute M(n,k) for these values:

  1. n≤9 and any k;
  2. k≤3 and any n;
  3. A selection of values for n≤50.
If the function doesn't know how to compute M(n,k) exactly, it will return an interval [M0(n,k),M1(n,k)] which we conjecture to contain the correct value. The difference between the two conjectured bounds is O(n-2). It is proved in our paper that M(n,k) is asymptotic to M0(n,k) if n and k go to infinity with k>Cn/log n for some C>1/6.

symmint.maple can be used in a Maple session (console or worksheet) by inputting it with the "read" command. It is a plain text file, so if you only want the numbers without running Maple you can just look at it.

 

Page Master: Brendan McKay, brendan.mckay@anu.edu.au

Up to the combinatorial data page