Computing Tutte Polynomials

The Tutte polynomial of a graph, also known as the partition function of the q -state Potts model is a 2-variable polynomial graph invariant of considerable importance in both combinatorics and statistical physics. It contains several other polynomial invariants, such as the chromatic polynomial and flow polynomial as partial evaluations, and various numerical invariants such as the number of spanning trees as complete evaluations. However despite its ubiquity, there are no widely available effective computational tools able to compute the Tutte polynomial of a general graph of reasonable size. In this article we describe the implementation of a program that exploits isomorphisms in the computation tree to extend the range of graphs for which it is feasible to compute their Tutte polynomials, and we demonstrate the utility of the program by finding counterexamples to a conjecture of Welsh on the location of the real flow roots of a graph.