Hamiltonian properties of polyhedra with few 3-cuts. A survey

DOI10.1016/j.disc.2018.06.015zbMath1392.05066OpenAlexW2811004539WikidataQ129606207 ScholiaQ129606207MaRDI QIDQ724894

Kenta Ozeki, Carol T. Zamfirescu, Nicolas Van Cleemput

Publication date: 26 July 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2018.06.015

zbMATH Keywords

triangulationHamiltonianpolyhedronplanar graph3-connected graphtraceableHamiltonian-connecteddecomposition tree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Related Items (8)

Every 4-Connected Graph with Crossing Number 2 is Hamiltonian ⋮ Circumscribing polygons and polygonizations for disjoint line segments ⋮ On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs ⋮ The ratio of the numbers of odd and even cycles in outerplanar graphs ⋮ Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey ⋮ Unnamed Item ⋮ Shortness coefficient of cyclically 4-edge-connected cubic graphs ⋮ Regular non-Hamiltonian polyhedral graphs

Cites Work

• Non-Hamiltonian cubic planar maps
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• Long cycles in 4-connected planar graphs
• The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices
• Scattering number and extremal non-Hamiltonian graphs
• A 1-tough nonhamiltonian maximal planar graph
• The traveling salesman problem: An overview of exact and approximate algorithms
• Planar and infinite hypohamiltonian and hypotraceable graphs
• Bridges and Hamiltonian circuits in planar graphs
• On a class of posets and the corresponding comparability graphs
• Planar cubic hypohamiltonian and hypotraceable graphs
• Some remarks on Jaeger's dual-hamiltonian conjecture
• 4-connected projective planar graphs are Hamiltonian
• Any maximal planar graph with only one separating triangle is Hamiltonian
• On Hamiltonian cycles in 4- and 5-connected plane triangulations
• Polyhedra with few 3-cuts are Hamiltonian
• Non-Hamiltonian triangulations with distant separating triangles
• Cycles in 4-connected planar graphs
• Non-hamiltonian \(5 \over 4\)-tough maximal planar graphs
• Cycles through 23 vertices in 3-connected cubic planar graphs
• Each maximal planar graph with exactly two separating triangles is Hamiltonian
• 2-edge-Hamiltonian-connectedness of 4-connected plane graphs
• Tough graphs and Hamiltonian circuits.
• Simple paths on polyhedra
• On the Strongest Form of a Theorem of Whitney for Hamiltonian Cycles in Plane Triangulations
• Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs
• Computing 2-Walks in Polynomial Time
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• A Theorem on Planar Graphs
• Hamilton cycles in maximal planar graphs
• Chordal and timbral morphologies using Hamiltonian cycles
• 5-Connected Toroidal Graphs are Hamiltonian-Connected
• On the number of hamiltonian cycles in a maximal planar graph
• A Combinatorial Decomposition Theory
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Hamiltonian cycles in planar triangulations with no separating triangles
• On certain Hamiltonian cycles in planar graphs
• Every 4-Connected Graph with Crossing Number 2 is Hamiltonian
• On the number of hamiltonian cycles in triangulations with few separating triangles
• Hamilton cycles in plane triangulations
• Nonhamiltonian 3-Connected Cubic Planar Graphs
• Reducibility among Combinatorial Problems
• Polytopes, graphs, and complexes
• On Hamiltonian Circuits
• A theorem on paths in planar graphs
• A theorem on paths in planar graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hamiltonian properties of polyhedra with few 3-cuts. A survey