International Journal of Mathematics and Mathematical Sciences
Volume 2004 (2004), Issue 6, Pages 273-283
doi:10.1155/S0161171204302206
Determinantal generating functions of colored spanning forests
1Department of Mathematics, University of Pittsburgh, Pittsburgh 15260, PA, USA
2Department of Mathematics, University of Pittsburgh at Bradford, Bradford 16701, PA, USA
Received 24 February 2003
Copyright © 2004 Gregory M. Constantine and Marius G. Buliga. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
The color type of a spanning forest of a graph with colored edges
is defined and, subsequently, it is proved that the generating function of such spanning forests is obtained as the formal expansion of a certain determinant. An analogous determinantal expansion yields the generating function of all spanning forests
of a given color type that contain a specific subforest. Algorithms are described for obtaining a list of all colored spanning trees and spanning forests of any graph with colored edges based on symbolic calculation.