On a conjecture of Faudree and Schelp
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916790630612992 |
|---|---|
| author | Goedgebeur, Jan Jooken, Jorik Provoost, Michiel Zamfirescu, Carol T. |
| author_facet | Goedgebeur, Jan Jooken, Jorik Provoost, Michiel Zamfirescu, Carol T. |
| contents | 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 \ge 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_09667 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On a conjecture of Faudree and Schelp Goedgebeur, Jan Jooken, Jorik Provoost, Michiel Zamfirescu, Carol T. Combinatorics 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 \ge 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. |
| title | On a conjecture of Faudree and Schelp |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.09667 |