Counting spanning trees on fractal graphs and their asymptotic complexity
Counting spanning trees on fractal graphs and their asymptotic complexity
复制标题
DOI：
10.1088/1751-8113/49/35/355101
复制
发表时间：
2016-09-02
影响因子：
2.1
通讯作者：
Tsougkas, Konstantinos
中科院分区：
文献类型：
--
作者：
Anema, Jason A.;Tsougkas, Konstantinos
利用谱抽取的方法和基尔霍夫矩阵树定理的一个修正版本，在定理3.4中给出了将图近似为一个完全对称的自相似结构的生成树个数的一个封闭形式的解。我们展示了如何频谱抽取意味着存在的渐近复杂性常数，并获得一些bounds.Examples计算包括Sierpinski垫片，一个非后临界有限模拟Sierpinski垫片，钻石分形，和hexagasket。对于每一个例子，渐近复杂性常数。
Using the method of spectral decimation and a modified version of Kirchhoff's matrix-tree theorem, a closed form solution to the number of spanning trees on approximating graphs to a fully symmetric self-similar structure on a finitely ramified fractal is given in theorem 3.4. We show how spectral decimation implies the existence of the asymptotic complexity constant and obtain some bounds for it. Examples calculated include the Sierpinski gasket, a non-post critically finite analog of the Sierpinski gasket, the Diamond fractal, and the hexagasket. For each example, the asymptotic complexity constant is found.