Hamiltonian cycles in linear-convex supergrid graphs

DOI10.1016/j.dam.2016.04.020zbMath1348.05117arXiv1506.00190OpenAlexW2963874483MaRDI QIDQ335338

Ruo-Wei Hung

Publication date: 2 November 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.00190

zbMATH Keywords

Hamiltonian cyclegrid graphlocally connectedcomputer sewing machinelinear-convex supergrid graphsupergrid graphtriangular grid graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Related Items (8)

A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole ⋮ The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs ⋮ A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes ⋮ The restrained domination and independent restrained domination in extending supergrid graphs ⋮ Restrained domination and its variants in extended supergrid graphs ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hamiltonian paths in some classes of grid graphs
• The Hamiltonian properties of supergrid graphs
• The total bondage number of grid graphs
• Approximating the longest paths in grid graphs
• Extending cycles in graphs
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• Hamiltonian properties of triangular grid graphs
• Hamiltonian circuits in interval graph generalizations
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Claw-free graphs---a survey
• Hamiltonian cycles in T-graphs
• Total domination number of grid graphs
• An efficient algorithm for constructing Hamiltonian paths in meshes
• The Hamiltonian circuit problem for circle graphs is NP-complete
• Algorithmic graph theory and perfect graphs
• Eulerian disjoint paths problem in grid graphs is NP-complete
• Bondage number of grid graphs
• On the broadcast independence number of grid graph
• The NP-completeness column: an ongoing guide
• Hamiltonian Properties of Grid Graphs
• Intersections of longest cycles in grid graphs
• Hamilton Paths in Grid Graphs

This page was built for publication: Hamiltonian cycles in linear-convex supergrid graphs