Barovich, Mark V.

Determining which graphs are hamiltonian is a central unsolved problem in graph theory. More generally, the study of long cycles in graphs has been extensive, and there are numerous results on the subject in the mathematical literature. In this dissertation, we survey several of these results. The study of long paths is related to the study of long cycles. In a graph in which every pair of vertices is connected by a long path, every edge lies on a long cycle. We prove that any set of four vertices lying on a common path in a 2-connected graph lie on a common long path, generalizing a result of Lovasz. We further exploit the relationship between long paths and long cycles to prove that the cycle spaces of a large class of hamiltonian graphs are generated by long cycles, partially proving a conjecture made by Bondy.