### Computing the number of h-edge spanning forests in complete bipartite graphs

*Rebecca J. Stones*

#### Abstract

Let f

_{m,n,h}be the number of spanning forests with h edges in the complete bipartite graph K_{m,n}. Kirchhoff's Matrix Tree Theorem implies f_{m,n,m+n-1}=m^{n-1}n^{m-1}when m ≥1 and n ≥1, since f_{m,n,m+n-1}is the number of spanning trees in K_{m,n}. In this paper, we give an algorithm for computing f_{m,n,h}for general m,n,h. We implement this algorithm and use it to compute all non-zero f_{m,n,h}when m ≤50 and n ≤50 in under 2 days.Full Text: PDF PostScript