A general method for computing Tutte polynomials of self-similar graphs

作者：Gong, Helin; Jin, Xian'an^*

来源：Physica A: Statistical Mechanics and Its Applications , 2017, 483: 117-129.

DOI：10.1016/j.physa.2017.04.073

• Tutte polynomial
• Self-similar
• Spanning tree
• Sierpinski gasket
• Potts model partition function

Self-similar graphs were widely studied in both combinatorics and statistical physics. Motivated by the construction of the well-known 3-dimensional Sierpinski gasket graphs, in this paper we introduce a family of recursively constructed self-similar graphs whose inner duals are of the self-similar property. By combining the dual property of the Tutte polynomial and the subgraph-decomposition trick, we show that the Tutte polynomial of this family of graphs can be computed in an iterative way and in particular the exact expression of the formula of the number of their spanning trees is derived. Furthermore, we show our method is a general one that is easily extended to compute Tutte polynomials for other families of self-similar graphs such as Farey graphs, 2-dimensional Sierpinski gasket graphs, Hanoi graphs, modified Koch graphs, Apollonian graphs, pseudofractal scale-free web, fractal scale-free network, etc.

• 出版日期2017-10-1
• 单位厦门大学