On an Extension of an Observation of Hamilton

Abstract

For a Hamiltonian graph $G$, the Hamiltonian cycle extension number of $G$ is the maximum positive integer $k$ for which every path of order $k$ or less is a subpath of some Hamiltonian cycle of $G$. The Hamiltonian cycle extension numbers of all Hamiltonian complete multipartite graphs are determined. Sharp lower bounds for the Hamiltonian cycle extension number of a Hamiltonian graph are presented in terms of its minimum degree and order, its size and the sum of the degrees of every two non-adjacent vertices. Hamiltonian cycle extension numbers are also determined for powers of cycles.