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

dmtcs:1248 - Discrete Mathematics & Theoretical Computer Science, May 12, 2014, Vol. 16 no. 1 - https://doi.org/10.46298/dmtcs.1248
Computing the number of h-edge spanning forests in complete bipartite graphsArticle

Authors: Rebecca Stones 1

  • 1 School of Mathematical Sciences [Clayton]

Let fm,n,h be the number of spanning forests with h edges in the complete bipartite graph Km,n. Kirchhoff\textquoterights 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.


Volume: Vol. 16 no. 1
Section: Analysis of Algorithms
Published on: May 12, 2014
Accepted on: July 23, 2015
Submitted on: October 6, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 412 times.
This article's PDF has been downloaded 817 times.