有关对称无权图生成树数目的拆分定理

The Factorization Theorems on the Number of Spanning Trees of Graphs with Some Symmetry

设G是一个对称平面图.Ciucu等证明了一个有关G的生成树数目的拆分定理,也就是G的生成树数目可用两个小图的生成树数目乘积来表示.在此基础上,提出了一种图变换,给出了图在这种变换下生成树数目的变化关系式,再结合矩阵-树定理给出了该拆分定理的一个简短证明.同时,受Zhang等证明的赋权图生成树权和的拆分定理启发,还给出了一个关于对称无权图生成树数目的等价拆分公式.

Let G be a plane graph with reflective symmetry.Ciucu,et al,proved a factorization theorem on the number of spanning trees of G.That is,the number of spanning treesof G can be expressed in terms of the product of the number of spanning trees of two smaller graphs.In this paper,we introduce a graph transformation and discuss its effect on the number of spanning trees,then by the matrix-tree theorem we give a short proof of above-mentioned factorization theorem.Motivated by a factorization theorem on the sum of weights of spanning trees of weighted graphs with some symmetry in Zhang et al,we further provide an equivalent factorization formula on the number of spanning trees of unweighted graphs with some symmetry.