Premium
Counting k ‐component forests of a graph
Author(s) -
Myrvold Wendy
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220704
Subject(s) - combinatorics , mathematics , spanning tree , planar graph , connected component , time complexity , discrete mathematics , dual graph , graph , tutte polynomial , line graph , voltage graph
We describe an algorithm for computing the number of k ‐component spanning forests of a graph G that runs in polynomial time for fixed k . The algorithm is based on earlier work by Liu and Chow. Our contributions are a simpler graph‐theoretic proof of their formula and a demonstration of how Jacobi's Theorem can be applied to improve the asymptotic time complexity. By matroid duality, the number of connected spanning subgraphs of cyclomatic number c of a planar graph equals the number of c + 1‐component forests in the dual. Thus, one application of this research is an algorithm for counting connected spanning unicyclic subgraphs of a planar graph. We show this can be done in time O(M(n)) , where M(n) is the time complexity of multiplying together two n by n matrices.