Characterizations of Highly Path-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 $\ell$ for which every path of order $\ell$ or less is a subpath of some Hamiltonian cycle in $G$. If the order of $G$ equals $n$, then it is known that $\text{hce}(G)=n$ if and only if $G$ is a cycle or a regular complete bipartite graph (when $n$ is even) or a complete graph. We present a complete characterization of Hamiltonian graphs of order $n$ that are $\ell$-path-Hamiltonian for each $\ell \in \{n-3,n-2,n-1,n\}$.