1
$\begingroup$

For given $n_1,n_2 \in \mathbb{N}$ let $K_{n_1,n_2}$ be the complete bipartite graph. I have seen a few sources proving that the number of spanning trees $t(K_{n_1,n_2})$ is given by $n_1^{n_2-1} n_2^{n_1-1}$.

For the complete connected graph $K_n$ even more is known. For given $d_1,...,d_n \in \mathbb{N}$ the number of spanning trees of $K_n$, where each vertex $v_i$ has degree $d_i$, is given by $$ {n-2 \choose d_1-1, ... ,d_n-1} \ . $$

I would be interested in a similar formula for the complete bipartite graph $K_{n_1,n_2}$. Is something like this known?

Any help is always much appreciated.

PS. I'm currently looking into the properties of certain $(n_1 \times n_2)$ random matrices and am rather astonished as to how much graph theory is needed. I'm rather new to graph theory so sorry, if I'm missing something simple.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Do you know about Prüfer sequences? (If not, see en.wikipedia.org/wiki/Pr%C3%BCfer_sequence) They also work for spanning trees of the complete bipartite graph. $\endgroup$
    – Sam Hopkins
    Commented Apr 12, 2022 at 19:25
  • 2
    $\begingroup$ See math.stackexchange.com/questions/3157546/… for more discussion $\endgroup$
    – Sam Hopkins
    Commented Apr 12, 2022 at 19:27
  • 2
    $\begingroup$ See J. W. Moon's Counting Labelled Trees, equation (2.2), math.ucla.edu/~pak/hidden/papers/…. This book is a great resource for anything to do with enumeration of labeled trees. $\endgroup$
    – Ira Gessel
    Commented Apr 12, 2022 at 21:50
  • $\begingroup$ Thank you! These are both very helpful. The proof from Bodendiek and Henn's Book is already enough to get the formula, but Moon's paper explicitly states the formula, which means a bit less effort for me. $\endgroup$
    – Ben Deitmar
    Commented Apr 13, 2022 at 7:29

0

Reset to default

You must log in to answer this question.