#### Date

2013

#### Document Type

Dissertation

#### Degree

Doctor of Philosophy

#### Department

Mathematics

#### First Adviser

Isakk, Garth

#### Other advisers/committee members

Skandera, Mark; Stanley, Lee; Baird, Henry

#### Abstract

The Hamiltonian path problem is to determine whether a graph has a Hamiltonian path. This problem is NP-complete in general. The path partition problem is to determine the minimum number of vertex-disjoint paths required to cover a graph. Since this problem is a generalization of the Hamiltonian path problem, it is also NP-complete in general. The k-fixed-endpoint path partition problem is to determine the minimum number of vertex-disjoint paths required to cover a graphG such that each vertex in a set T of k vertices is an endpoint of a path. Since this problem is a generalization of the Hamiltonian path problem and path partition problem, it is also NP-complete in general. For certain classes of graphs, there exist efficient algorithms for the k-fixed-endpoint path partition problem. We consider this problem restricted to trees, threshold graphs, block graphs, and unit interval graphs and show min-max theorems which characterize the k-fixed-endpoint pathpartition number.

#### Recommended Citation

Baker, Breeanne Alyse, "The k-fixed-endpoint path partition problem" (2013). *Theses and Dissertations*. 1420.

http://preserve.lehigh.edu/etd/1420