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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.313--326
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01179216
Contributeur : Hélène Lowinger <>
Soumis le : mercredi 22 juillet 2015 - 09:15:09
Dernière modification le : mercredi 10 janvier 2018 - 09:42:46
Document(s) archivé(s) le : vendredi 23 octobre 2015 - 10:24:35

Fichier

dmtcs-16-1-19.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

92

Téléchargements de fichiers

105