THE TUTTE POLYNOMIAL
Dr Steven Noble, Department of Mathematical Sciences, Brunel University

Abstract: We show how a variety of graph invariants including the number of spanning trees, network reliability and the number of vertex colourings are related via the Tutte Polynomial. We define a generalisation of the Tutte Polynomial using weighted graphs. This specialises to many more graph invariants including the matching polynomial and the symmetric function generalisation of the chromatic polynomial introduced by Stanley. We discuss whether this polynomial determines trees.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 5 March 2002.