Honors Theses

Date of Award

2014

Document Type

Undergraduate Thesis

Department

Mathematics

First Advisor

Laura Sheppardson

Relational Format

Dissertation/Thesis

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.

Included in

Mathematics Commons

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.