On an Extension of an Observation of Hamilton

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.