Characterizations of Highly Path-Hamiltonian Graphs

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\}\).