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

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

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

Abstract: Let K_n^m(n≥2,m≥1) be the complete multigraph n vertices, where any two different vertices, are connected by exactly m edges. K_n^m+G (or K_n^m-G) is defined as the resulting graph obtained from K_n^m by adding (or removing) all edges of a subgraph G in K_n^m . Based on Kirchhoff’s cele-brated matrix-tree theorem, Nikolopoulos and Papadopoulos, obtained the number of spanning trees of K_n^m±G as follows: τ(K_n^m±G)=m(mn)^n-p-2det[mnI_p±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 τ(K_n^m±G) were also shown when G is the complete graph, the cycle, the path and the complete bi-partite graph respectively.