Cycles in Graphs

In 1856, Sir William Rowan Hamilton invented a game consisting of a dodecahedron each of whose twenty vertices were labeled with a name of a city. The objective of the game was to travel along the edges of the dodecahedron, visiting each city exactly once and return to the initial city. In the language of modern graph theory, the objective of the game was to find a Hamilton cycle in the graph of the dodecahedron. The game did not have big commercial success, but it opened a new area in graph theory with many important applications.

This talk will be a survey of some old and new results in this subject with emphasis on sufficient conditions for pancyclicity, the existence of a second Hamilton cycle, and maximally non-Hamiltonian graphs.