The Hamiltonian properties of supergrid graphs

DOI10.1016/j.tcs.2015.08.024zbMath1330.05093OpenAlexW2188309853MaRDI QIDQ497690

Ruo-Wei Hung, Shang-Ju Chan, Chih-Chia Yao

Publication date: 25 September 2015

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

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

zbMATH Keywords

grid graphsupergrid graphtriangular grid graphalphabet supergrid graphcomputerized sewing machineHamiltonian propertiesrectangular supergrid graph

Mathematics Subject Classification ID

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

Related Items (9)

Hamiltonian cycles in linear-convex supergrid graphs ⋮ 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 ⋮ Hamiltonian connectivity of diagonal grid graphs ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs

Cites Work

• Hamiltonian paths in some classes of grid graphs
• The total bondage number of grid graphs
• Approximating the longest paths in grid graphs
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• Conditional edge-fault Hamiltonicity of augmented cubes
• 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
• 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
• Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Hamiltonian properties of supergrid graphs