Date

2019

Document Type

Dissertation

Degree

Doctor of Philosophy

Department

Mathematics

First Adviser

Isaak, Garth

Abstract

The Hamiltonian path problem is a well-known NP-complete graph theory problem which is to determine whether or not it is possible to find a spanning path in a graph. Some variations on this problem include the 1HP and 2HP problems, which are to determine whether or not it is possible to find a Hamiltonian path in a graph if one or two endpoints of the path are fixed, respectively. Both problems are also NP-complete for graphs in general, though like the Hamiltonian path problem, they are polynomially solvable on certain types of graphs. 2-trees are a specific type of graph for which the 1HP, 2HP, and traditional Hamiltonian path problems are polynomially solvable. It is known that 2-trees have a Hamiltonian cycle if and only if they are 1-tough. However, the analogous statement for Hamiltonian paths does not hold. We will structurally characterize 2HP on 2-trees, and then use these results to structurally characterize 1HP and HP on 2-trees. We will define a family of 2-trees such that any 2-tree has a Hamiltonian path if and only if it does not contain any graph from that family as an induced graph.

Share

COinS