On $\ell$-Path-Hamiltonian and $\ell$-Path-Pancyclic Graphs

Abstract

Let $G$ be a Hamiltonian graph of order $n\ge 3$. For an integer $\ell$ with $1\le \ell \le n$, the graph $G$ is $\ell$-path-Hamiltonian if every path of order $\ell$ lies on a 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 lies on a Hamiltonian cycle of $G$. For an integer $\ell$ with $2\le \ell \le n-1$, the graph $G$ is $\ell$-path-pancyclic if every path of order $\ell$ in $G$ lies on a cycle of every length from $\ell +1$ to $n$. (Thus, a $2$-path-pancyclic graph is edge-pancyclic.) A graph $G$ of order $n\ge 3$ is path-pancyclic if $G$ is $\ell$-path-pancyclic for each integer $\ell$ with $2\le \ell \le n-1$. In this paper, we present a brief survey of known results on these two parameters and investigate the $\ell$-path-Hamiltonian graphs and $\ell$-path-pancyclic graphs having small minimum degree and small values of $\ell$. Furthermore, highly path-pancyclic graphs are characterized and several well-known classes of $2$-path-pancyclic graphs are determined. The relationship among these two parameters and other well-known Hamiltonian parameters is investigated along with some open questions in this area of research.