Tutte polynomial of a fractal scale-free lattice

2014/10/29 by Hanlin Chen, Chen, Hanlin, Yuanhua Liao +3
Computer Science · Mathematics · Physics and Astronomy · #Advanced Combinatorial Mathematics #Advanced Mathematical Theories and Applications #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph)

paper · pdf · doi:10.48550/arxiv.1410.7988

openalex publication_date 2014/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 combinatorics and statistical physics. The computation of this invariant for a graph is NP-hard in general. In this paper, based on their self-similar structures, we recursively describe the Tutte polynomials of an infinite family of scale-free lattices. Furthermore, we give some exact analytical expressions of the Tutte polynomial for several special points at (X,Y)-plane.

Related

• Tutte Polynomials and Related Asymptotic Limiting Functions for Recursive Families of Graphs
• The Tutte polynomial via lattice point counting
• Tutte polynomial, complete invariant, and theta series
• Algorithm for computing the partition function of the Potts model for SP-graphs
• Computing the Tutte polynomial in vertex-exponential time