Higher-dimensional counterexamples to Hamiltonicity
Higher-dimensional counterexamples to Hamiltonicity
For $d \ge 2$, we show that all graphs of $d$-polytopes have a Hamiltonian line graph if and only if $d \ne 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 $3n$ vertices in whose line graph any simple path is shorter than $10 n^α$, for some constant $α<1$. Moreover, we give four elementary counterexamples of plausible extensions to simplicial complexes of four famous results in Hamiltonian graph theory.
Bruno Benedetti、Marta Pavelka
数学
Bruno Benedetti,Marta Pavelka.Higher-dimensional counterexamples to Hamiltonicity[EB/OL].(2025-07-02)[2025-07-16].https://arxiv.org/abs/2207.06891.点此复制
评论