4
$\begingroup$

I am trying to count the number of $(d_v,d_c)$ regular bipartite graphs. To be specific, let $n,m,d_v,d_c$ be positive integers such that $$n\times d_v=m\times d_c.$$ Then, what is the number of bipartite graphs $\mathcal{G}=(L\cup R, E)$, where $L$ is the set of left vertices, $R$ is the set of right vertices with the property that each left vertex has $d_v$ edges incident on it, and each right vertex has $d_c$ edges incident on it (allowing parallel edges, i.e., there can be more than one edge for a given pair of vertices)? Can one find a general expression for this?

This problem can be reformulated as a ball and bin problem in the following way: We have a total of $nd_v$ balls, of $n$ colors, with $d_v$ balls of each color. What is the number of ways of putting these balls in $m$ nonidentical bins so that each bin has exactly $d_c$ balls? Let me denote this number $\psi(n,d_v,d_c)$ A quick thought about this gives me the following bounds: $$ \frac{(nd_v)!}{\left(d_v! \right)^n(d_c!)^m}\leq\psi(n,d_v,d_c)\leq \frac{(nd_v)!}{\left(d_v! \right)^n}. $$ Can one do better?

I think there must be some work that has addressed this problem but I have not been able to find anything. Any help would be appreciated.

$\endgroup$
2
$\begingroup$

There is no useful exact formula except for tiny $d_v$ or $d_c$. The best asymptotic results appear in this paper of Canfield and McKay for dense matrices and this paper of Greenhill and McKay for sparse matrices. There is an unsolved gap between the two ranges. The first paper has a conjecture that probably holds for all values of the parameters.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.