2-edge-Hamiltonian-connectedness of 4-connected plane graphs

DOI10.1016/J.EJC.2013.06.033MaRDI QIDQ2509769zbMATH OpenOpenAlexFDO

Authors Kenta Ozeki, Petr Vrána

Publication date 29 July 2014

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

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

zbMATH Keywords

2-edge-Hamiltonian-connected graphHamiltonian cycle

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• 4-connected projective planar graphs are Hamiltonian
• 4-connected projective-planar graphs are Hamiltonian-connected
• Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs
• 4-connected projective-planar graphs are Hamiltonian-connected

Cites work

• 4-connected projective planar graphs are Hamiltonian
• 4-connected projective-planar graphs are Hamiltonian-connected
• A theorem on paths in planar graphs
• A Theorem on Planar Graphs
• An Infinite Class of Hypohamiltonian Graphs
• Connectivity, genus, and the number of components in vertex-deleted subgraphs
• Disjoint paths, planarizing cycles, and spanning walks
• Five-connected toroidal graphs are Hamiltonian
• Graphs with 1-hamiltonian-connected cubes
• Hamilton paths in toroidal graphs
• scientific article; zbMATH DE number 1002024 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3414331 (Why is no real title available?)
• Hypohamiltonian and hypotraceable graphs
• Measuring the vulnerability for classes of intersection graphs
• MinimumK-hamiltonian graphs
• Minimumk-hamiltonian graphs, II
• On a class of posets and the corresponding comparability graphs
• On Hamilton cycles in certain planar graphs
• Polytopes, graphs, and complexes
• Scattering number and extremal non-Hamiltonian graphs
• The 2-hamiltonian cubes of graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs
• Tough graphs and Hamiltonian circuits.

Cited in

(13)

• 4-connected projective planar graphs are Hamiltonian
• Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
• Hamiltonian-connectedness of triangulations with few separating triangles
• scientific article; zbMATH DE number 866659 (Why is no real title available?)
• Computing Tutte paths
• On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs
• Counting cycles in planar triangulations
• 2-edge-Hamilton-connectedness of complete hypercube-like networks
• On platypus graphs and the Steiner-Deogun property
• On k-edge-Hamilton-connected line graphs
• 4-connected 1-planar chordal graphs are Hamiltonian-connected
• 2-edge Hamiltonian connectedness: characterization and results in data center networks
• Hamiltonian properties of polyhedra with few 3-cuts. A survey

This page was built for publication: 2-edge-Hamiltonian-connectedness of 4-connected plane graphs

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