TY - JOUR

T1 - Tutte polynomials and related asymptotic limiting functions for recursive families of graphs

AU - Chang, Shu Chiuan

AU - Shrock, Robert

N1 - Funding Information:
R.S. thanks Profs. Dominic Welsh and Marc Noy for their organization of the stimulating CRM Workshop on Tutte Polynomials. This research was partially supported by the NSF grant PHY-00-98527.

PY - 2004

Y1 - 2004

N2 - We prove several theorems concerning Tutte polynomials T(G, x, y) for recursive families of graphs. In addition to its interest in mathematics, the Tutte polynomial is equivalent to an important function in statistical physics, the partition function of the q-state Potts model, Z(G, q, v), where v is a temperature-dependent variable. These theorems determine the general structure of the Tutte polynomial for a homogeneous cyclic clan graph Jm (Kr) comprised of a chain of m copies of the complete graph Kr such that the linkage L between each successive pair of Kr's is a join, and r and m are arbitrary. The explicit calculation of the case r = 3 (for arbitrary m) is presented. The continuous accumulation set of the zeros of Z in the limit m → ∞ is considered. Further, we present calculations of two special cases of Tutte polynomials, namely flow and reliability polynomials, for homogeneous cyclic clan graphs and discuss the respective continuous accumulation sets of their zeros in the limit m → ∞. Special valuations of Tutte polynomials give enumerations of spanning trees and acyclic orientations. Two theorems are presented that determine the number of spanning trees on Jm (Kr) and the graph Im (Kr comprised of a chain of m copies of the complete graph Kr such that the linkage between each successive pair of Kr's is the identity linkage, and r and m are arbitrary. We report calculations of the number of acyclic orientations for strips of the square lattice and use these to suggest an improved lower bound on the exponential growth rate of the number of these acyclic orientations.

AB - We prove several theorems concerning Tutte polynomials T(G, x, y) for recursive families of graphs. In addition to its interest in mathematics, the Tutte polynomial is equivalent to an important function in statistical physics, the partition function of the q-state Potts model, Z(G, q, v), where v is a temperature-dependent variable. These theorems determine the general structure of the Tutte polynomial for a homogeneous cyclic clan graph Jm (Kr) comprised of a chain of m copies of the complete graph Kr such that the linkage L between each successive pair of Kr's is a join, and r and m are arbitrary. The explicit calculation of the case r = 3 (for arbitrary m) is presented. The continuous accumulation set of the zeros of Z in the limit m → ∞ is considered. Further, we present calculations of two special cases of Tutte polynomials, namely flow and reliability polynomials, for homogeneous cyclic clan graphs and discuss the respective continuous accumulation sets of their zeros in the limit m → ∞. Special valuations of Tutte polynomials give enumerations of spanning trees and acyclic orientations. Two theorems are presented that determine the number of spanning trees on Jm (Kr) and the graph Im (Kr comprised of a chain of m copies of the complete graph Kr such that the linkage between each successive pair of Kr's is the identity linkage, and r and m are arbitrary. We report calculations of the number of acyclic orientations for strips of the square lattice and use these to suggest an improved lower bound on the exponential growth rate of the number of these acyclic orientations.

UR - http://www.scopus.com/inward/record.url?scp=0346401578&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346401578&partnerID=8YFLogxK

U2 - 10.1016/S0196-8858(03)00077-0

DO - 10.1016/S0196-8858(03)00077-0

M3 - Article

AN - SCOPUS:0346401578

SN - 0196-8858

VL - 32

SP - 44

EP - 87

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

IS - 1-2

ER -