Regular pseudographs

Question

Is there a counting known for $3$-regular (or any $n$-regular) pseudo graph of a given order $|V|$? An asymptotic result for connected (or disconnected) graphs is good enough. It would be even better to know an asymptotic counting with $2$-labeling, i.e. pseudo graph a given order $|V|$ labelled with two labels (say 0,1).

Answer 1

There is an article by Catherine Greenhill (UNSW Sydney) and Brendan McKay (ANU Canberra), Asymptotic enumeration of sparse multigraphs with given degrees

Theorem 1.1 yields a more general results, but Corollary 1.2 should be want you wanted. If I'm not mistaken, using their notation, you should input $y_1=x_2=x_3=1$, and you obtain that the number of $k$ regular multigraphs is, for $k=o(n^{1/2})$, $$\frac{(kn)!}{(kn/2)!2^{kn/2}(k!)^n}\exp(-Q(k,n)+O(k^2/n)),$$ where $$Q(k,n)= \frac{-1}{4}(k-1)(k+1)+\frac{k^3}{12n}.$$

Answer 2

I think that this is essentially due to

Read, R. C., The enumeration of locally restricted graphs. I, J. Lond. Math. Soc. 34, 417-436 (1959). ZBL0089.18301.

see https://oeis.org/A129427 Nowadays, combinatorial species provide a nice framework. For $r$ vertices, you want $$ \langle E_r(X E_3(Y)), E_{3r/2}(E_2(Y))\rangle_Y, $$ where $E_r$ is the species of sets of $r$ elements (with cycle index series, or Frobenius character, $h_r$). Think of $X$ as the species of vertices and $Y$ as of the species of half-edges. Then $X E_3(Y)$ are the $3$ half-edges incident to an edge, and $E_r(X E_3(Y))$ are sets of $r$ such things. On the other hand, $E_{3r/2}(E_2(Y))$ is the species of partitions of the label set of half-edges into pairs. Taking the scalar product with respect to $Y$ means that we want to superimpose these two structures, and then forget about the labels.

The good thing about the formula is that you get labelled and unlabelled structures in one go. The bad thing is that it is terrible for computations.