An enumerating function for spanning forests with color restrictions

Bapat, R. B. ; Constantine, G. (1992) An enumerating function for spanning forests with color restrictions Linear Algebra and its Applications, 173 . pp. 231-237. ISSN 0024-3795

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/0...

Related URL: http://dx.doi.org/10.1016/0024-3795(92)90431-9

Abstract

Consider a graph in which each edge is assigned a color. A list of spanning trees with all edges of distinct colors is obtained as the formal expansion of certain mixed discriminants. An enumerating function for spanning trees with prescribed number of edges of each color is derived. The result generalizes the matrix-tree theorem of Kirchhoff. In particular, a list of spanning forests with k trees of a graph with n + 1 vertices is obtained as the formal expansion of the sum of the principal minors of order n + 1 - k in the Kirchhoff matrix associated to the graph.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:78310
Deposited On:19 Jan 2012 06:31
Last Modified:19 Jan 2012 06:31

Repository Staff Only: item control page