Some Results on Tutte Polynomials with Applications Including Spanning Trees

R. Shrock, YITP, Stony Brook University

Abstract

Many interesting connections between statistical mechanics and graph theory
involve the Tutte polynomial, which is equivalent to the Potts model partition
function.  Special cases of the Tutte polynomial include the chromatic
polynomial, counting the ways of coloring the vertices of a graph so that no
two adjacent vertices have the same color, the flow polynomial, and others
graph-theoretic quantities.  One valuation of the Tutte polynomial yields the
number of spanning trees $N_{ST}$ on a graph.  Here we present exact
calculations of Tutte polynomials for various families of graphs.  We give a 
theorem concerning classes of lattice graphs $\Lambda$ for which $N_{ST}$ grows
exponentially, like $e^{n z_\Lambda}}$, as the number of vertices $n \to
\infty$. We evaluate the exponential growth constants $z_\Lambda$ analytically
and/or numerically for a number of lattices and discuss their dependence on
properties of the lattices.