Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01179216
Contributor : Hélène Lowinger <>
Submitted on : Wednesday, July 22, 2015 - 9:15:09 AM
Last modification on : Wednesday, January 29, 2020 - 12:00:02 PM
Long-term archiving on: : Friday, October 23, 2015 - 10:24:35 AM

File

dmtcs-16-1-19.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01179216, version 1

Collections

Citation

Rebecca Stones. Computing the number of h-edge spanning forests in complete bipartite graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.313--326. ⟨hal-01179216⟩

Share

Metrics

Record views

191

Files downloads

1962