Connectivity, toughness, and hamiltonicity of simplicial polytopes
Abstract
For every d≥4, every prescribed connectivity r≥ d, and every ε>0, we construct a simplicial d-polytope whose graph has connectivity exactly r, is nontraceable, and has toughness less than ε. Thus the classical theorems of Whitney (1931) and Tutte (1956), which guarantee hamiltonicity under sufficiently high connectivity in dimension three, have no higher-dimensional counterpart. This answers a question posed by Bojan Mohar in 2001 on whether sufficiently high connectivity guarantees hamiltonicity of $4$-polytopal graphs and the connectivity questions raised by Ikegami, Maezawa, and Zamfirescu in 2021. For fixed d≥4, r≥ d, and integer k≥2, the examples can be chosen to have no closed spanning walk with at most k visits per vertex, no spanning tree with degrees at most k, and nontraceable prisms. For fixed d and r, we obtain graphs on n vertices whose longest paths and cycles contain O(√n) vertices. Consequently, the family of simplicial d-polytopes with connectivity exactly r has Grünbaum--Walther shortness coefficient zero and shortness exponent at most 1/2.
Related
- Asymptotic connectivity, hamiltonicity and toughness
- Toughness Bounds for Fractional Hamiltonicity and Resistance Positivity
- Equifacetted polytopes whose facets are products of simplices: The simplicial prism case
- Solid-angle formulas for simplicial cones and random shifted sections of polytopes
- Hilbert functions over the exterior algebra and f-vectors in higher rank I: Amata-Crupi monomial modules, Kozlov polytopes, and r-vectors of simplicial complexes
BibTeX
@misc{pinedavillavicencio2026connectivity,
title = {{Connectivity, toughness, and hamiltonicity of simplicial polytopes}},
author = {Guillermo Pineda-Villavicencio},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12836},
eprint = {2610.12836},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12836},
}
RIS
TY - UNPB
TI - Connectivity, toughness, and hamiltonicity of simplicial polytopes
AU - Guillermo Pineda-Villavicencio
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.12836
UR - https://arxiv.org/abs/2610.12836
AB - For every d≥4, every prescribed connectivity r≥ d, and every ε>0, we construct a simplicial d-polytope whose graph has connectivity exactly r, is nontraceable, and has toughness less than ε. Thus the classical theorems of Whitney (1931) and Tutte (1956), which guarantee hamiltonicity under sufficiently high connectivity in dimension three, have no higher-dimensional counterpart. This answers a question posed by Bojan Mohar in 2001 on whether sufficiently high connectivity guarantees hamiltonicity of $4$-polytopal graphs and the connectivity questions raised by Ikegami, Maezawa, and Zamfirescu in 2021. For fixed d≥4, r≥ d, and integer k≥2, the examples can be chosen to have no closed spanning walk with at most k visits per vertex, no spanning tree with degrees at most k, and nontraceable prisms. For fixed d and r, we obtain graphs on n vertices whose longest paths and cycles contain O(√n) vertices. Consequently, the family of simplicial d-polytopes with connectivity exactly r has Grünbaum--Walther shortness coefficient zero and shortness exponent at most 1/2.
ER -