Hamiltonian cycles in T-graphs

DOI10.1007/S004540010051MaRDI QIDQ1580773zbMATH OpenOpenAlexFDO

Authors John R. Reay, Tudor Zamfirescu

Publication date 23 January 2001

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004540010051

zbMATH Keywords

Archimedean triangular tilingHamiltonian cycleT-graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Review text

The vertices and polygonal edges of the planar Archimedean tiling \(3^6\) of the plane is called the triangular tiling graph (TTG). A subgraph \(G\) of TTG is linearly convex if, for every line \(L\) which contains an edge of TTG, the set \(L \cap G\) is a (possibly degenerated or empty) line segment. A T-graph is any nontrivial, finite, linearly convex, 2-connected subgraph of TTG. The authors prove that with only one exeption, any T-graph contains a Hamiltonian cycle.

Recommendations

• scientific article; zbMATH DE number 568821
• scientific article; zbMATH DE number 4152419
• Hamiltonian cycles in regular graphs
• Hamilton cycles in some vertex-transitive graphs
• Hamilton cycles in Trivalent Cayley graphs
• Hamiltonian cycles in n‐extendable graphs
• Hamilton Cycles in Oriented Graphs
• On the cyclic properties of Hamiltonian graphs
• Hamilton cycles in tensor product of graphs
• Hamiltonian cycles in 1-tough graphs

Cited in

(15)

• The Hamiltonian connectivity of rectangular supergrid graphs
• Rikudo is NP-complete
• Hamiltonian cycles in linear-convex supergrid graphs
• On k-trestles in polyhedreal graphs
• The Hamiltonian properties of supergrid graphs
• Archimedean tiling graphs with Gallai's property.
• TSP tour domination and Hamilton cycle decompositions of regular digraphs
• The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs
• 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
• A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes
• Hamiltonian (s, t)-paths in solid supergrid graphs
• The Hamiltonian path graph is connected for simple s,t paths in rectangular grid graphs
• Characterizations and clique coloring of edge intersection graphs on a triangular grid
• Hamiltonicity of rectangular grid graphs (meshes) with an L-shaped hole
• Hamiltonian properties of triangular grid graphs

This page was built for publication: Hamiltonian cycles in T-graphs

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