## Computing the Tutte Polynomial of Graphs |

**John Adams**

Union College

April 3, 2006

4:45 pm

Bailey Hall 201

Pastries and drinks will be served in Bailey 204 at 4:30

A graph defined by a set of vertices and edges can be represented by a polynomial in two variables, called the Tutte polynomial. This polynomial has generated much interest not only because of the many attributes of the graph that can be derived from it but also because of its link to the partition function of a well known model in statistical mechanics. The Tutte polynomial of a graph can be defined in one of two ways. The first is in terms of a sum over all its spanning subgraphs and the second is a recursive process of contractions and deletions of its edges. In this talk, I will introduce the Tutte polynomial and present my algorithm for the computation of the Tutte polynomial using the idea of linear dependence of edges in a graph.

For additional information, send e-mail to math@union.edu or call (518) 388-6246.

Union College Math Department Home PageComments to: math@union.edu Created automatically on: Fri Apr 20 21:58:54 EDT 2018 |