2025/06/11 by Jan Goedgebeur, Goedgebeur, Jan, Jorik Jooken +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2506.09667
openalex publication_date 2025/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1976 Faudree and Schelp conjectured that in a hamiltonian-connected graph on n vertices, any two distinct vertices are connected by a path of length k for every k ≥ n/2. In 1978 Thomassen constructed a (non-cubic and non-planar) family of counterexamples, showing that there exist hamiltonian-connected n-vertex graphs containing two vertices with no path of length n-2 between them. We complement this result by describing cubic planar counterexamples on 6p+16 vertices, each containing vertices between which there is no path of any odd length greater than 1 and at most 4p+9. Motivated by a remark of Thomassen about a gap in the cycle spectrum of hamiltonian-connected graphs, we also describe an infinite family of hamiltonian-connected graphs with many gaps in the first half of their cycle spectra.