Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-97-09 June 1997

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:

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:

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.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html