MATH Seminar

Title: 3-Connected, Claw-Free, Generalized Net-Free Graphs are Hamiltonian
Defense: Dissertation
Speaker: Susan Janiszewski of Emory University
Contact: Susan Janiszewski, sjanisz@emory.edu
Date: 2012-02-29 at 3:00PM
Venue: W306
Download Flyer
Abstract: Given a family $\mathcal{F} = \{H_1, H_2, \dots, H_k\}$ of graphs, we say that a graph is $\mathcal{F}$-free if $G$ contains no subgraph isomorphic to any $H_i$, $i = 1,2,\dots, k$. The graphs in the set $\mathcal{F}$ are known as {\it forbidden subgraphs}. The main goal of this dissertation is to further classify pairs of forbidden subgraphs that imply a 3-connected graph is hamiltonian. First, the number of possible forbidden pairs is reduced by presenting families of graphs that are 3-connected and not hamiltonian. Of particular interest is the graph $K_{1,3}$, also known as the {\it claw}, as we show that it must be included in any forbidden pair. Secondly, we show that 3-connected, $\{K_{1,3}, N_{i,j,0}\}$-free graphs are hamiltonian for $i,j \ne 0, i+j \le 9$ and 3-connected, $\{K_{1,3}, N_{3,3,3}\}$-free graphs are hamiltonian, where $N_{i,j,k}$, known as the {\it generalized net}, is the graph obtained by rooting vertex-disjoint paths of length $i$, $j$, and $k$ at the vertices of a triangle. These results combined with previous known results give a complete classification of generalized nets such that claw-free, net-free implies a 3-connected graph is hamiltonian.