On ℓ-Path-Hamiltonian and ℓ-Path-Pancyclic Graphs: Results and Problems

摘要

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