Discrete Mathematics & Theoretical Computer Science, Vol 16, No 1 (2014)

Font Size:  Small  Medium  Large

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

Rebecca J. Stones


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