Spanning trees on graphs and lattices in d dimensions
Spanning trees on graphs and lattices in d dimensions
复制标题
DOI：
10.1088/0305-4470/33/21/303
复制
发表时间：
2000-06-02
期刊：
影响因子：
--
通讯作者：
Wu, FY
中科院分区：
文献类型：
--
作者：
Shrock, R;Wu, FY
考虑图和格上生成树的计数问题。我们得到了N-ST的生成树个数的界，并建立了不同图或格的生成树个数的不等式。给出了d ≥ 2维格上生成树计数的一般公式，并应用于超立方、体心立方、面心立方和特殊平面格，包括kagome格、diced格、4-8-8（浴室瓷砖）格、Union Jack格和3-12-12格.这导致封闭形式的表达式为N-ST这些有限大小的晶格。本文证明了一个关于图类和格类L的定理，当顶点数n>无穷大时，N-ST与exp（nz（L））相似，其中z（L）是一个有限的非零常数.这包括在任何空间维度上的格的体积极限，以及在某些维度上长度趋于无穷而其他维度上长度有限的格的部分。对于我们所考虑的格，我们精确地计算z（L），并讨论z（L）对d和格配位数的依赖性。Pie还建立了将z（L）与平面晶格的临界伊辛模型的自由能联系起来的关系。
The problem of enumerating spanning trees on graphs and lattices is considered. We obtain bounds on the number of spanning trees N-ST and establish inequalities relating the numbers of spanning trees of different graphs or lattices. A general formulation is presented for the enumeration of spanning trees on lattices in d greater than or equal to 2 dimensions, and is applied to the hypercubic, body-centred cubic, face-centred cubic and specific planar lattices including the kagome, diced, 4-8-8 (bathroom-tile), Union Jack and 3-12-12 lattices. This leads to closed-form expressions for N-ST for these lattices of finite sizes. We prove a theorem concerning the classes of graphs and lattices L with the property that N-ST similar to exp(nz(L)) as the number of vertices n --> infinity, where z(L) is a finite non-zero constant. This includes the bulk limit of lattices in any spatial dimension, and also sections of lattices whose lengths in some dimensions go to infinity while others are finite. We evaluate z(L) exactly for the lattices we consider, and discuss the dependence of z(L) on d and the lattice coordination number. Pie also establish a relation connecting z(L) to the free energy of the critical Ising model for planar lattices.