Enumeration of spanning trees of graphs with rotational symmetry
Enumeration of spanning trees of graphs with rotational symmetry
复制标题
旋转对称图生成树的枚举
DOI：
10.1016/j.jcta.2010.12.007
复制
发表时间：
2011-05-01
影响因子：
1.1
通讯作者：
Zhang, Fuji
中科院分区：
文献类型：
--
作者：
Yan, Weigen;Zhang, Fuji
有限图中生成树的枚举方法是一个涉及数学和物理各个领域的问题，已经被许多数学家和物理学家研究过。如果图G的n阶循环群是G的自同构群的子群，则图G是n旋转对称的。物理学家最近研究了在环面边界条件下正则格上生成树的枚举及其渐近生长常数的计算。一个自然的问题是考虑具有圆柱形边界条件的格的生成树的枚举问题，即所谓的旋转对称图。假设G是N阶旋转对称图，所有轨道大小为N，有N个同构诱导子图G(0)， G(1)，…, G (n - 1)。本文证明了当j不等于i - 1，i + 1 （mod n）时G(i)与G(j)之间不存在边，则G的生成树的个数可以用n个图的生成树的加权枚举D(i)的乘积来表示，当i = 0,1，…， n - 1，其中如果i = 0， D(i)有n /n个顶点，否则有n /n + 1个顶点。作为应用，我们得到了具有圆柱边界条件的五格的生成树数和渐近树数熵的显式表达式。(C) 2010出版的爱思唯尔公司。
Methods of enumeration of spanning trees in a finite graph, a problem related to various areas of mathematics and physics, have been investigated by many mathematicians and physicists. A graph G is said to be n-rotational symmetric if the cyclic group of order n is a subgroup of the automorphism group of G. Some recent studies on the enumeration of spanning trees and the calculation of their asymptotic growth constants on regular lattices with toroidal boundary condition were carried out by physicists. A natural question is to consider the problem of enumeration of spanning trees of lattices with cylindrical boundary condition, which are the so-called rotational symmetric graphs. Suppose G is a graph of order N with n-rotational symmetry and all orbits have size n, which has n isomorphic induced subgraphs G(0), G(1), ..., G(n-1). In this paper, we prove that if there exists no edge between G(i) and G(j) for j not equal i - 1, i + 1 (mod n), then the number of spanning trees of G can be expressed in terms of the product of the weighted enumerations of spanning trees of n graphs D(i)'s for i = 0, 1, ..., n - 1, where D(i) has N/n vertices if i = 0 and N/n + 1 vertices otherwise. As applications we obtain explicit expressions for the numbers of spanning trees and asymptotic tree number entropies for five lattices with cylindrical boundary condition in the context of physics. (C) 2010 Published by Elsevier Inc.