Hamiltonian cycles in linear-convex supergrid graphs

DOI10.1016/J.DAM.2016.04.020zbMATH Open1348.05117arXiv1506.00190OpenAlexW2963874483MaRDI QIDQ335338FDOQ335338

Authors: Ruo-Wei Hung 

Publication date: 2 November 2016

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

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.

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

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

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)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Claw-free graphs---a survey
• Algorithmic graph theory and perfect graphs
• Title not available (Why is that?)
• Hamilton Paths in 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
• Title not available (Why is that?)
• Total domination number of grid graphs
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Hamiltonian circuits in interval graph generalizations
• Hamiltonian cycles in T-graphs
• An efficient algorithm for constructing Hamiltonian paths in meshes
• The Hamiltonian circuit problem for circle graphs is NP-complete
• Eulerian disjoint paths problem in grid graphs is NP-complete
• Bondage number of grid graphs
• On the broadcast independence number of grid graph
• Title not available (Why is that?)
• The NP-completeness column: an ongoing guide
• Hamiltonian Properties of Grid Graphs
• Intersections of longest cycles in grid graphs
• Hamiltonian paths in some classes of grid graphs
• The Hamiltonian properties of supergrid graphs
• The total bondage number of grid graphs
• Hamiltonian properties of triangular 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)