# Centre for Discrete and Applicable Mathematics

## CDAM Research Report, LSE-CDAM-97-09

June 1997

The Tutte Polynomial as a Growth Function

Norman Biggs

Abstract

The Tutte polynomial of a graph G can be defined as a sum taken over the set $\Sigma(G)$ of spanning trees of G:

$${\cal T}(G;x,y) = \sum_{T \in \Sigma(G)} x^{i(T)} y^{j(T)},$$

where i(T) and j(T) are non-negative integers associated with the spanning tree T. Partial evaluations of the Tutte polynomial occur in a wide variety of seemingly unrelated situations: the graph-colouring polynomial and the Jones polynomial of a knot or link being just two examples. Recently it has been observed that the set $\Sigma(G)$ is in bijective correspondence with several other sets of objects associated with G. In fact all these sets are instances of an abelian group K(G), which has a natural presentation in terms of G. The main result of this paper is that the reciprocal polynomial of ${\cal T}(G;1,z)$ is the growth function ${\cal L}(z)$ of K(G) with respect to its natural presentation:

$$z^{c} {\cal T}(G; 1,z^{-1}) = {\cal L}(z) = \sum_{g \in K(G)} z^{L(g)},$$

where c is the cycle-rank of G and L(g) is the length of g in K(G). The basis of the proof is the observation that manipulations involving the natural set of generators and relations for K(G) correspond to moves in the so-called `dollar game' on G.

If you would like a free copy of this report, please send the number of this report, LSE-CDAM-97-09, together with your name and postal address to:
 CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. Phone: +44(0)-171-955 7732. Fax: +44(0)-171-955 6877. Email: info@maths.lse.ac.uk

 Introduction to the CDAM Research Report Series. CDAM Homepage.