Graphs and Combinatorics Дискретная математика и комбинаторика

Higher-dimensional counterexamples to Hamiltonicity

Bruno Benedetti, Marta Pavelka
Springer Nature · 2025-12-04 · DOI 10.1007/s00373-025-02988-5

Аннотация

Abstract For $$d \ge 2$$ d ≥ 2 , we show that all graphs of d -polytopes have a Hamiltonian line graph if and only if $$d \ne 3$$ d ≠ 3 : We exhibit a graph of a 3-polytope on 252 vertices whose line graph does not even have Hamiltonian paths. Adapting a construction by Grünbaum and Motzkin, for large n we also construct simple 3-polytopes on 3 n vertices in whose line graph any simple path is shorter than $$10 n^{\alpha }$$ 10 n α , for some constant $$\alpha <1$$ α < 1 . Moreover, we give four elementary counterexamples of plausible extensions to simplicial complexes of four famous results in Hamiltonian graph theory.

Читать у издателя →