On Hamiltonian Cycle Extension in Cubic Hamiltonian Graphs

Abstract

A Hamiltonian graph $G$ is said to be $\ell$-path-Hamiltonian, where $\ell$ is a positive integer less than or equal to the order of $G$, if every path of order $\ell$ in $G$ is a subpath of some Hamiltonian cycle in $G$. The Hamiltonian cycle extension number of $G$ is the maximum positive integer $L$ for which $G$ is $\ell$-path-Hamiltonian for every integer $\ell$ with $1\le \ell \le L$. Hamiltonian cycle extension numbers are determined for several well-known cubic Hamiltonian graphs. It is shown that if $G$ is a cubic Hamiltonian graph with girth $g$, where $3\le g\le 7$, then $G$ is $\ell$-path-Hamiltonian only if $1\le \ell \le g$.