关于图类K_n^m±G的生成树数目

On the Number of Spanning Trees of Graphs K_n^m±G

记Knm(n≥2,m≥1)是n个顶点的完全多重图,即任意两个顶点间有且仅有m条边相连。Knm+G (或Knm-G)为在Knm基础上再添加(或从中删除)子图的对应边得到的图。Nikolopoulos和Papadopoulos利用Kirchhoff矩阵–树定理给出了Knm+G生成树数目τ(Knm±G)=m(mn)n-p-2det[mnIp±L(G)]。本文利用线性代数技巧(一个有关矩阵和的行列式计算公式),对该定理给出了一种新的简洁证法。并给出当G为完全图、圈、路、二部图时Knm±G生成数目的计算公式。

Let Knm(n≥2,m≥1) be the complete multigraph n vertices, where any two different vertices, are connected by exactly m edges. Knm+G (or Knm-G) is defined as the resulting graph obtained from Knm by adding (or removing) all edges of a subgraph G in Knm . Based on Kirchhoff’s cele-brated matrix-tree theorem, Nikolopoulos and Papadopoulos, obtained the number of spanning trees of Knm±G as follows: τ(Knm±G)=m(mn)n-p-2det[mnIp±L(G)] . In this paper, by using some linear algebra techniques (a special formula on a determinant of two matrices), a new simple proof for above-mentioned counting formula was given. Furthermore, some new results on τ(Knm±G) were also shown when G is the complete graph, the cycle, the path and the complete bi-partite graph respectively.