Enumeration of spanning trees of graphs with rotational symmetry

CORC > 厦门大学 > 数学科学－已发表论文

	Enumeration of spanning trees of graphs with rotational symmetry
	Yan, Weigen ; Zhang, Fuji ; Zhang FJ(张福基)
刊名	http://dx.doi.org/10.1016/j.jcta.2010.12.007
	2011-05
关键词	REFLECTIVE SYMMETRY PERFECT MATCHINGS LATTICES MODELS TRANSITION ENTROPY NUMBER
英文摘要	NSFC [10771086, 10831001]; Fujian Province University; 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.
语种	英语
内容类型	期刊论文
源URL	[http://dspace.xmu.edu.cn/handle/2288/66268]
专题	数学科学－已发表论文
推荐引用方式 GB/T 7714	Yan, Weigen,Zhang, Fuji,Zhang FJ. Enumeration of spanning trees of graphs with rotational symmetry[J]. http://dx.doi.org/10.1016/j.jcta.2010.12.007,2011.
APA	Yan, Weigen,Zhang, Fuji,&张福基.(2011).Enumeration of spanning trees of graphs with rotational symmetry.http://dx.doi.org/10.1016/j.jcta.2010.12.007.
MLA	Yan, Weigen,et al."Enumeration of spanning trees of graphs with rotational symmetry".http://dx.doi.org/10.1016/j.jcta.2010.12.007 (2011).