Tutte Polynomial of Scale-Free Networks

详细信息    查看全文

• 作者：Hanlin Chen ; Hanyuan Deng
• 刊名：Journal of Statistical Physics
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：163
• 期：4
• 页码：714-732
• 全文大小：920 KB
• 刊物类别：Physics and Astronomy
• 刊物主题：Physics
  Statistical Physics
  Mathematical and Computational Physics
  Physical Chemistry
  Quantum Physics
  
• 出版者：Springer Netherlands
• ISSN：1572-9613
• 卷排序：163

文摘

The Tutte polynomial of a graph, or equivalently the q-state Potts model partition function, is a two-variable polynomial graph invariant of considerable importance in both statistical physics and combinatorics. The computation of this invariant for a graph is NP-hard in general. In this paper, we focus on two iteratively growing scale-free networks, which are ubiquitous in real-life systems. Based on their self-similar structures, we mainly obtain recursive formulas for the Tutte polynomials of two scale-free networks (lattices), one is fractal and “large world”, while the other is non-fractal but possess the small-world property. Furthermore, we give some exact analytical expressions of the Tutte polynomial for several special points at (x, y)-plane, such as, the number of spanning trees, the number of acyclic orientations, etc.KeywordsTutte polynomialPotts modelSpanning treesAcyclic orientationsAsymptotic growth constantScale-free network