AN ENUMERATING FUNCTION FOR SPANNING FORESTS WITH COLOR RESTRICTIONS

被引：8

作者：

BAPAT, RB ^{[1
]}

CONSTANTINE, G ^{[1
]}

机构：

[1] UNIV PITTSBURGH,CTR STAT,PITTSBURGH,PA 15260

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 1992年 / 173卷

关键词：

D O I：

10.1016/0024-3795(92)90431-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：231 / 237

页数：7