Computing the Tutte Polynomial of Graphs
April 3, 2006
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.
|Union College Math Department Home Page|
Comments to: email@example.com
Created automatically on: Tue Oct 23 17:38:00 EDT 2018