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

DOI10.1016/J.EJC.2021.103395zbMATH1469.05097OpenAlexW3178022067WikidataQ114184727MaRDI QIDQ2048366FDOQ2048366

Authors Gunnar Brinkmann, Nico 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)

Recommendations

• Polyhedra with few 3-cuts are Hamiltonian
• Counting Hamiltonian cycles in planar triangulations
• Number of Hamiltonian cycles in planar triangulations
• Hamiltonian cycles in 4-connected plane triangulations with few 4-separators
• Cycles in 5-connected triangulations

Cites work

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

Cited in

(7)

• Hamiltonian cycles and 1-factors in 5-regular graphs
• Hamiltonian cycles in 4-connected planar and projective planar triangulations with few 4-separators
• Regular graphs with few longest cycles
• On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs
• Counting cycles in planar triangulations
• \(4\)-regular \(4\)-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles
• Counting Hamiltonian cycles in planar triangulations

Describes a project that uses

Uses Software

• House of Graphs
• plantri

This page was built for publication: 4-connected polyhedra have at least a linear number of Hamiltonian cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2048366)