Five-connected toroidal graphs are Hamiltonian

DOI10.1006/JCTB.1996.1713MaRDI QIDQ1354120zbMATH OpenOpenAlexFDO

Authors Robin Thomas, Xingxing Yu

Publication date 20 July 1997

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1996.1713

zbMATH Keywords

connectivityHamilton cyclepolynomial time algorithmrepresentativitytorusTutte path

Mathematics Subject Classification ID

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

Review text

We prove that every edge in a 5-connected graph embedded in the torus is contained in a Hamilton cycle. Our proof is constructive and implies a polynomial time algorithm for finding a Hamilton cycle.

Recommendations

• 5-Connected Toroidal Graphs are Hamiltonian-Connected
• Hamilton paths in toroidal graphs
• Hamilton cycles in 4-connected troidal triangulations
• On Hamiltonian cycles in 4- and 5-connected plane triangulations
• Hamilton cycles in 2-connected \([5,3]\)-graphs

Cited in

(31)

• Spanning Eulerian subgraphs of bounded degree in triangulations
• Hamiltonian cycles in polyhedral maps
• The circumference of a graph with no \(K_{3,t}\)-minor. II
• Counting Hamiltonian cycles in planar triangulations
• Subhamiltonian toroidal graphs
• 4-connected projective-planar graphs are Hamiltonian-connected
• \([a,b]\)-factors of graphs on surfaces
• Recent advances on the Hamiltonian problem: survey III
• Hamilton paths in toroidal graphs
• 2-edge-Hamiltonian-connectedness of 4-connected plane graphs
• On the circumference of 3-connected cubic triangle-free plane graphs
• Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
• Face-width of embedded graphs
• Hamilton cycles in 4-connected troidal triangulations
• Hamiltonian cycles in bipartite quadrangulations on the torus
• Disjoint paths, planarizing cycles, and spanning walks
• 5-Connected Toroidal Graphs are Hamiltonian-Connected
• scientific article; zbMATH DE number 4049683 (Why is no real title available?)
• Computing Tutte paths
• scientific article; zbMATH DE number 7603356 (Why is no real title available?)
• 2- and 3-factors of graphs on surfaces
• scientific article; zbMATH DE number 6475975 (Why is no real title available?)
• Criticality of counterexamples to toroidal edge-Hamiltonicity
• The 2-extendability of graphs on the projective plane, the torus and the Klein bottle
• The decycling number of a line graph
• The 2-extendability of 5-connected graphs on the Klein bottle
• What is on his mind?
• A note on traversing specified vertices in graphs embedded with large representativity
• Hamiltonicity of doubly semi-equivelar maps on the torus
• Chords of longest circuits in locally planar graphs
• The circumference of a graph with no \(K_{3,t}\)-minor

This page was built for publication: Five-connected toroidal graphs are Hamiltonian

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