4-connected polyhedra have at least a linear number of Hamiltonian cycles

DOI10.1016/j.ejc.2021.103395zbMath1469.05097OpenAlexW3178022067WikidataQ114184727 ScholiaQ114184727MaRDI QIDQ2048366

Gunnar Brinkmann, Nicolas Van Cleemput

Publication date: 5 August 2021

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2021.103395

zbMATH Keywords

Hamiltonian cycles3-connected plane graphs

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Eulerian and Hamiltonian graphs (05C45)

Related Items

Counting Hamiltonian cycles in planar triangulations ⋮ Regular Graphs with Few Longest Cycles ⋮ Hamiltonian Cycles in 4-Connected Planar and Projective Planar Triangulations with Few 4-Separators ⋮ Hamiltonian cycles and 1-factors in 5-regular graphs ⋮ On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs ⋮ 4-regular 4-connected Hamiltonian graphs with few Hamiltonian cycles

Uses Software

• House of Graphs
• plantri

Cites Work

• Polyhedra with few 3-cuts are Hamiltonian
• House of Graphs: a database of interesting graphs
• Cycles in 5-connected triangulations
• A Theorem on Planar Graphs
• On the number of hamiltonian cycles in a maximal planar graph
• On the number of hamiltonian cycles in triangulations with few separating triangles
• Hamilton cycles in plane triangulations
• On Hamilton cycles in certain planar graphs
• A theorem on paths in planar graphs