4-connected polyhedra have at least a linear number of hamiltonian cycles. (October 2021)

• Record Type: Journal Article
• Authors: Brinkmann, Gunnar; Van Cleemput, Nico
• Is Part Of: European journal of combinatorics. Volume 97(2021)
• Publication Date: 2021-10
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103395
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Although polyhedra can have much fewer edges than triangulations, many results about hamiltonicity proven for triangulations also hold for polyhedra. The most famous of these results is surely Whitney's result from 1931 that 4-connected triangulations are hamiltonian, which was 25 years later generalised to 4-connected polyhedra by Tutte. Nevertheless the only known bounds for the number of hamiltonian cycles in 4-connected polyhedra are constant, though for triangulations a lower bound of | V | ∕ ( log 2 | V | ) was already proven in 1979 and improved to a linear bound in 2018. In this article we prove linear lower bounds for 4-connected polyhedra and polyhedra with at most one 3-cut and sufficiently many edges.