Hamiltonian properties of triangular grid graphs

DOI10.1016/j.disc.2007.11.040zbMath1158.05040MaRDI QIDQ998354

Frank Werner, Yury L. Orlovich, Valery S. Gordon

Publication date: 28 January 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2007.11.040

zbMATH Keywords

local connectivity; NP-completeness; Hamiltonian graph; triangular grid graph

Mathematics Subject Classification ID

92C40: Biochemistry, molecular biology

92E10: Molecular structure (graph-theoretic methods, methods of differential topology, etc.)

05C45: Eulerian and Hamiltonian graphs

Related Items

Hamiltonian paths in \(L\)-shaped grid graphs, Hamiltonian cycles in linear-convex supergrid graphs, Word-representability of face subdivisions of triangular grid graphs, Hamiltonian paths in some classes of grid graphs, The Hamiltonian properties of supergrid graphs, Hamiltonian properties of locally connected graphs with bounded vertex degree, Not being (super)thin or solid is hard: A study of grid Hamiltonicity, Many-to-many two-disjoint path covers in cylindrical and toroidal grids, Domination with decay in triangular matchstick arrangement graphs, A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole, An Improved Strategy for Exploring a Grid Polygon

Cites Work

• Extending cycles in graphs
• Claw-free graphs---a survey
• Hamiltonian cycles in T-graphs
• A strengthening of Kikustapos;s theorem
• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• Hamilton Paths in Grid Graphs
• Channel assignment and multicolouring of the induced subgraphs of the triangular lattice
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item