Enumerating spanning trees of graphs with an involution
Enumerating spanning trees of graphs with an involution
复制标题
枚举具有对合图的生成树
DOI：
10.1016/j.jcta.2008.10.004
复制
发表时间：
2009-04-01
影响因子：
1.1
通讯作者：
Yan, Weigen
中科院分区：
文献类型：
--
作者：
Zhang, Fuji;Yan, Weigen
作为Ciucu和本文作者[M. Ciucu，W.G.杨福君，张福君，具有反射对称的平面图的生成树的个数，J. Combin. Theory Ser.A112（2005）105-116]的基础上，本文研究了具有允许不动点的对合的赋权图的生成树的计数问题。证明了：如果G是一个有对合的加权图，则G的生成树的权和可以表示为两个由G的对合决定的较小尺寸的加权图的生成树的权和的乘积.作为应用，我们列举了几乎完全二部图、几乎完全图、Mobius梯和两个图的几乎并的生成树。(C)2008年爱思唯尔公司All rights reserved.
As the extension of the previous work by Ciucu and the present authors [M. Ciucu, W.G. Yan, F.J. Zhang, The number of spanning trees of plane graphs with reflective symmetry, J. Combin. Theory Ser. A 112 (2005) 105-116], this paper considers the problem of enumeration of spanning trees of weighted graphs with an involution which allows fixed points. We show that if G is a weighted graph with an involution, then the sum of weights of spanning trees of G can be expressed in terms of the product of the sums of weights of spanning trees of two weighted graphs with a smaller size determined by the involution of G. As applications, we enumerate spanning trees of the almost-complete bipartite graph, the almost-complete graph, the Mobius ladder, and the almost-join of two copies of a graph. (C) 2008 Elsevier Inc. All rights reserved.