Finding and enumerating Hamilton cycles in 4-regular graphs

DOI10.1016/J.TCS.2011.04.038zbMATH Open1226.05143OpenAlexW2008391796MaRDI QIDQ638522FDOQ638522

Authors: Heidi Gebauer 

Publication date: 12 September 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.04.038

Recommendations

• \(4\)-regular \(4\)-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles
• Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
• Hamiltonian paths and cycles in some 4-uniform hypergraphs
• Hamiltonian cycles in regular graphs
• scientific article; zbMATH DE number 31019
• On the minimum number of Hamiltonian cycles in regular graphs
• Hamiltonicity of 4-connected graphs
• Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• Finding Hamiltonian cycles in certain planar graphs

zbMATH Keywords

traveling salesman problemHamilton cyclesregular graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• A Dynamic Programming Approach to Sequencing Problems
• An Improved Exact Algorithm for Cubic Graph TSP
• Title not available (Why is that?)
• The Traveling Salesman Problem for Cubic Graphs
• The Travelling Salesman Problem in Bounded Degree Graphs
• Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs
• On the number of crossing-free matchings, (cycles, and partitions)
• On the number of Hamilton cycles in bounded degree graphs

Cited In (17)

• Hamiltonian paths and cycles in some 4-uniform hypergraphs
• An improved exact algorithm for TSP in graphs of maximum degree 4
• An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
• Title not available (Why is that?)
• Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
• Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs
• Parameterized algorithms in smooth 4-regular Hamiltonian graphs
• Exact algorithms for finding longest cycles in claw-free graphs
• Solution to an open problem on 4-ordered Hamiltonian graphs
• Generating 4-regular Hamiltonian plane graphs
• A new upper bound for the traveling salesman problem in cubic graphs
• Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
• Estimation of the number of Hamiltonian cycles in regular graphs of special type
• On the minimum number of Hamiltonian cycles in regular graphs
• On the number of Hamilton cycles in bounded degree graphs
• \(4\)-regular \(4\)-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles

This page was built for publication: Finding and enumerating Hamilton cycles in 4-regular graphs

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