Hamiltonian properties of triangular grid graphs

DOI10.1016/j.disc.2007.11.040zbMath1158.05040WikidataQ57633903 ScholiaQ57633903MaRDI 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

Unnamed Item, Longest (s, t)-paths in L-shaped grid graphs, Hamiltonian paths in \(L\)-shaped grid graphs, The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs, 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids, 2-Trees: Structural insights and the study of Hamiltonian paths, A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes, 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, The Hamiltonian connectivity of rectangular supergrid graphs, The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs, The complexity of quantum circuit mapping with fixed parameters, Hamilton-connectivity of line graphs with application to their detour index, Hamilton-connectedness and Hamilton-laceability of planar geometric graphs with applications, Efficient \(( t , r )\) broadcast dominating sets of the triangular lattice, 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, Restrained domination and its variants in extended supergrid graphs, An Improved Strategy for Exploring a Grid Polygon

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Locally connected graphs
• Hamilton Paths in Grid Graphs
• Channel assignment and multicolouring of the induced subgraphs of the triangular lattice