International Journal of Mathematics and Mathematical Sciences
Volume 2004 (2004), Issue 6, Pages 273-283

Determinantal generating functions of colored spanning forests

Gregory M. Constantine1 and Marius G. Buliga2

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.


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.