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

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

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)

Cites Work

• Reducibility among Combinatorial Problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Title not available (Why is that?)
• The traveling salesman problem: An overview of exact and approximate algorithms
• Title not available (Why is that?)
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• Title not available (Why is that?)
• A Combinatorial Decomposition Theory
• Cycles through 23 vertices in 3-connected cubic planar graphs
• Any maximal planar graph with only one separating triangle is Hamiltonian
• Each maximal planar graph with exactly two separating triangles is Hamiltonian
• Title not available (Why is that?)
• A Theorem on Planar Graphs
• 4-connected projective planar graphs are Hamiltonian
• Simple paths on polyhedra
• A theorem on paths in planar graphs
• Planar and infinite hypohamiltonian and hypotraceable graphs
• Tough graphs and Hamiltonian circuits.
• On a class of posets and the corresponding comparability graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Scattering number and extremal non-Hamiltonian graphs
• On Hamiltonian Circuits
• Bridges and Hamiltonian circuits in planar graphs
• Hamiltonian cycles in planar triangulations with no separating triangles
• Hamilton cycles in plane triangulations
• Title not available (Why is that?)
• Polytopes, graphs, and complexes
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• A theorem on paths in planar graphs
• Non-Hamiltonian cubic planar maps
• Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs
• Title not available (Why is that?)
• Long cycles in 4-connected planar graphs
• The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices
• A 1-tough nonhamiltonian maximal planar graph
• Planar cubic hypohamiltonian and hypotraceable graphs
• Some remarks on Jaeger's dual-hamiltonian conjecture
• 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
• 2-edge-Hamiltonian-connectedness of 4-connected plane graphs
• Book embedding of projective-planar graphs
• On the strongest form of a theorem of Whitney for Hamiltonian cycles in plane triangulations
• Computing 2-Walks in Polynomial Time
• Title not available (Why is that?)
• 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
• On certain Hamiltonian cycles in planar graphs
• Title not available (Why is that?)
• Every 4-Connected Graph with Crossing Number 2 is Hamiltonian
• On the number of hamiltonian cycles in triangulations with few separating triangles
• Title not available (Why is that?)
• Nonhamiltonian 3-Connected Cubic Planar Graphs

Cited In (9)

• Every 4-Connected Graph with Crossing Number 2 is Hamiltonian
• Regular non-Hamiltonian polyhedral graphs
• Circumscribing polygons and polygonizations for disjoint line segments
• 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
• Polyhedra with few 3-cuts are Hamiltonian
• Shortness coefficient of cyclically 4-edge-connected cubic graphs
• Title not available (Why is that?)
• Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey

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)