Computing the number of h-edge spanning forests in complete bipartite graphs
Rebecca J. Stones
Abstract
Let fm,n,h be the number of spanning forests
with h edges in the complete bipartite graph
Km,n. Kirchhoff's Matrix Tree Theorem implies
fm,n,m+n-1=mn-1 nm-1
when m ≥1 and n ≥1, since
fm,n,m+n-1 is the number of spanning trees in
Km,n. In this paper, we give an algorithm for
computing fm,n,h for general
m,n,h. We implement this algorithm and use it to compute
all non-zero fm,n,h when m
≤50 and n ≤50 in under
2 days.
Full Text: PDF PostScript