Hamiltonian cycles in linear-convex supergrid graphs

DOI10.1016/J.DAM.2016.04.020MaRDI QIDQ335338zbMATH OpenOpenAlexFDO

Authors 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 cyclelocally connectedgrid graphcomputer sewing machinelinear-convex supergrid graphsupergrid graphtriangular grid graph

Mathematics Subject Classification ID

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

Abstract: A supergrid graph is a finite induced subgraph of the infinite graph associated with the two-dimensional supergrid. The supergrid graphs contain grid graphs and triangular grid graphs as subgraphs. The Hamiltonian cycle problem for grid and triangular grid graphs was known to be NP-complete. In the past, we have shown that the Hamiltonian cycle problem for supergrid graphs is also NP-complete. The Hamiltonian cycle problem on supergrid graphs can be applied to control the stitching trace of computerized sewing machines. In this paper, we will study the Hamiltonian cycle property of linear-convex supergrid graphs which form a subclass of supergrid graphs. A connected graph is called $k$-connected if there are $k$ vertex-disjoint paths between every pair of vertices, and is called locally connected if the neighbors of each vertex in it form a connected subgraph. In this paper, we first show that any 2-connected, linear-convex supergrid graph is locally connected. We then prove that any 2-connected, linear-convex supergrid graph contains a Hamiltonian cycle.

Recommendations

• The Hamiltonian properties of supergrid graphs
• The Hamiltonian connectivity of rectangular supergrid graphs
• The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs
• scientific article; zbMATH DE number 5543678
• Hamiltonian properties of triangular grid graphs

Cites work

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

Cited in

(10)

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

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

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