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

DOI10.1016/J.DISC.2018.06.015zbMATH Open1392.05066OpenAlexW2811004539WikidataQ129606207 ScholiaQ129606207MaRDI QIDQ724894FDOQ724894

Authors Kenta Ozeki, Carol T. Zamfirescu, Nico 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

triangulationpolyhedronHamiltonianplanar graphtraceableHamiltonian-connecteddecomposition tree3-connected graph

Mathematics Subject Classification ID

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

Recommendations

• Polyhedra with few 3-cuts are Hamiltonian
• Hamiltonian-connectedness of triangulations with few separating triangles
• Hamilton cycles in plane triangulations
• On Hamilton cycles in certain planar graphs
• scientific article; zbMATH DE number 3910429

Cites work

• scientific article; zbMATH DE number 1002024 (Why is no real title available?)
• scientific article; zbMATH DE number 5077174 (Why is no real title available?)
• scientific article; zbMATH DE number 4110708 (Why is no real title available?)
• scientific article; zbMATH DE number 3458515 (Why is no real title available?)
• scientific article; zbMATH DE number 3577225 (Why is no real title available?)
• scientific article; zbMATH DE number 1156578 (Why is no real title available?)
• scientific article; zbMATH DE number 1536530 (Why is no real title available?)
• scientific article; zbMATH DE number 786140 (Why is no real title available?)
• scientific article; zbMATH DE number 889961 (Why is no real title available?)
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• scientific article; zbMATH DE number 3414331 (Why is no real title available?)
• 2-edge-Hamiltonian-connectedness of 4-connected plane graphs
• 4-connected projective planar graphs are Hamiltonian
• 5-Connected Toroidal Graphs are Hamiltonian-Connected
• A 1-tough nonhamiltonian maximal planar graph
• A Combinatorial Decomposition Theory
• A Theorem on Planar Graphs
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• A theorem on paths in planar graphs
• A theorem on paths in planar graphs
• Any maximal planar graph with only one separating triangle is Hamiltonian
• Book embedding of projective-planar graphs
• Bridges and Hamiltonian circuits in planar graphs
• Chordal and timbral morphologies using Hamiltonian cycles
• Computing 2-walks in polynomial time
• Cycles in 4-connected planar graphs
• Cycles through 23 vertices in 3-connected cubic planar graphs
• Each maximal planar graph with exactly two separating triangles is Hamiltonian
• Every 4-connected graph with crossing number 2 is Hamiltonian
• Hamilton cycles in maximal planar graphs
• Hamilton cycles in plane triangulations
• Hamiltonian cycles in planar triangulations with no separating triangles
• Long cycles in 4-connected planar graphs
• Non-Hamiltonian cubic planar maps
• Non-Hamiltonian triangulations with distant separating triangles
• Non-hamiltonian \(5 \over 4\)-tough maximal planar graphs
• Nonhamiltonian 3-Connected Cubic Planar Graphs
• On Hamiltonian Circuits
• On Hamiltonian cycles in 4- and 5-connected plane triangulations
• On a class of posets and the corresponding comparability graphs
• On certain Hamiltonian cycles in 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
• On the strongest form of a theorem of Whitney for Hamiltonian cycles in plane triangulations
• Planar and infinite hypohamiltonian and hypotraceable graphs
• Planar cubic hypohamiltonian and hypotraceable graphs
• Polyhedra with few 3-cuts are Hamiltonian
• Polytopes, graphs, and complexes
• Reducibility among combinatorial problems
• Scattering number and extremal non-Hamiltonian graphs
• Simple paths on polyhedra
• Some remarks on Jaeger's dual-hamiltonian conjecture
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices
• The traveling salesman problem: An overview of exact and approximate algorithms
• Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs
• Tough graphs and Hamiltonian circuits.

Cited in

(10)

• Polyhedra with few 3-cuts are Hamiltonian
• The ratio of the numbers of odd and even cycles in outerplanar graphs
• On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs
• Every 4-connected graph with crossing number 2 is Hamiltonian
• Circumscribing polygons and polygonizations for disjoint line segments
• Shortness coefficient of cyclically 4-edge-connected cubic graphs
• Types of triangle in Hamiltonian triangulations and an application to domination and \(k\)-walks
• Regular non-Hamiltonian polyhedral graphs
• Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
• scientific article; zbMATH DE number 7559209 (Why is no real title available?)

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

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