The Tutte Polynomial Formula for the Class of Twisted Wheel Graphs

Hall, Amanda (2014) The Tutte Polynomial Formula for the Class of Twisted Wheel Graphs. Undergraduate thesis, under the direction of Laura Sheppardson from Mathematics, The University of Mississippi .

Preview

Text THESIS_AmandaHall2014Final.pdf Download (400kB) | Preview

Abstract

The 20th century work of William T. Tutte developed a graph polynomial that is modernly known as the Tutte polynomial. Graph polynomials, such as the Tutte polynomial, the chromatic polynomial, and the Jones polynomial, are at the heart of combinatorical and algebraic graph theory and can be used as tools with which to study graph invariants. Graph invariants, such as order, degree, size, and connectivity which are defined in Section 2, are graph properties preserved under all isomorphisms of a graph. Thus any graph polynomial is not dependent upon a particular labeling or drawing but presents relevant information about the abstract structure of the graph. The Tutte polynomial is the most general graph polynomial that satisfies the recurrence relationship of deletion and contraction. Deletion and contraction, collectively known as the reduction operations and defined in Section 2, are two important actions that con be performed upon a graph in order to aid in the computation of the graph polynomial of interest. The deletion and contraction recurrence relationship states that for every edge e of a graph G, the polynomial of G equals the sum of the polynomial of G delete e and the polynomial of G contract e. Even with the help of these reduction operations, the Tutte polynomial of a graph can be hard to compute with only pen and paper, leading to occasions in which researchers approach the task of developing a formula for the Tutte polynomial of some family of graphs; i.e. a collection of graphs that adhere to common properties. In this thesis, we review the work necessary to compute the Tutte polynomial of the class of fan graphs and the class of wheel graphs and then add to the collection known formulas by computing the formula for the Tutte polynomial of the class of twisted wheel graphs.

Actions (login required)

View Item