Enumeration of spanning trees of graphs with rotational symmetry

摘要

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 Gi and Gj for j≠i-1,i+1(modn), 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 Di has N vertices if i=0 and 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.