zbMATH — the first resource for mathematics

Hamiltonian properties of triangular grid graphs. (English) Zbl 1158.05040
Summary: A triangular grid graph is a finite induced subgraph of the infinite graph associated with the two-dimensional triangular grid. In 2000, J.R. Reay and T. Zamfirescu [Discrete Comput. Geom. 24, No. 2-3, 497–502 (2000; Zbl 0953.05040)] showed that all 2-connected, linearly-convex triangular grid graphs (with the exception of one of them) are hamiltonian. The only exception is a graph \(D\) which is the linearly-convex hull of the Star of David. We extend this result to a wider class of locally connected triangular grid graphs. Namely, we prove that all connected, locally connected triangular grid graphs (with the same exception of graph \(D\)) are hamiltonian. Moreover, we present a sufficient condition for a connected graph to be fully cycle extendable. We also show that the problem Hamiltonian Cycle is NP-complete for triangular grid graphs.

05C45 Eulerian and Hamiltonian graphs
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
92C40 Biochemistry, molecular biology
Full Text: DOI
[1] Agarwala, R.; Batzoglou, S.; Dančík, V.; Decatur, S.E.; Farach, M.; Hannenhalli, S.; Skiena, S., Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model, J. comput. biology, 4, 275-296, (1997) · Zbl 1321.92051
[2] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Macmillan London, Elsevier, New York · Zbl 1134.05001
[3] Chartrand, G.; Pippert, R., Locally connected graphs, Casopis pest. mat., 99, 158-163, (1974) · Zbl 0278.05113
[4] Clark, L., Hamiltonian properties of connected locally connected graphs, Congr. numer., 32, 199-204, (1981)
[5] des Cloizeaux, J.; Jannik, G., Polymers in solution: their modelling and structure, (1987), Clarendon Press Oxford
[6] Faudree, R.J.; Flandrin, E.; Ryjáček, Z., Claw-free graphs — A survey, Discrete math., 164, 87-147, (1997) · Zbl 0879.05043
[7] Garey, M.R.; Johnson, D.S., Computers and intractability. A guide to the theory of NP-completeness, (1979), W.H. Freeman and Co. San Francisco, CA · Zbl 0411.68039
[8] Grünbaum, B.; Shephard, G.C., Tilings and patterns: an introduction, (1989), W.H. Freeman New York · Zbl 0746.52001
[9] Havet, F., Channel assignment and multicoloring of the induced subgraphs of the triangular lattice, Discrete math., 233, 219-231, (2001) · Zbl 0983.05031
[10] Hendry, G.R.T., A strengthening of kikust’s theorem, J. graph theory, 13, 257-260, (1989) · Zbl 0668.05042
[11] Hendry, G.R.T., Extending cycles in graphs, Discrete math., 85, 59-72, (1990) · Zbl 0714.05038
[12] Itai, A.; Papadimitriou, C.H.; Szwarcfiter, J.L., Hamiltonian paths in grid graphs, SIAM J. comput., 11, 676-686, (1982) · Zbl 0506.05043
[13] Lenhart, W.; Umans, C., Hamiltonian cycles in solid grid graphs, (), 496-505
[14] Lua, R.; Borovinskiy, A.L.; Grosberg, A.Yu., Fractal and statistical properties of large compact polymers: A computational study, Polymer, 45, 717-731, (2004)
[15] Oberly, D.J.; Sumner, D.P., Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian, J. graph theory, 3, 351-356, (1979) · Zbl 0424.05036
[16] Orlovich, Yu.L., Kikust – hendry type conditions for Hamiltonian graphs, Tr. inst. mat., 3, 149-156, (1999), (in Russian) · Zbl 0949.05050
[17] Orlovich, Yu.L., On locally connected graphs whose maximal vertex degree is at most four, Vestsi nats. akad. navuk belarusi. ser. fiz.-mat. navuk, 3, 97-100, (1999), (in Russian)
[18] Orlovich, Yu.L.; Gordon, V.S.; Werner, F., Hamiltonian cycles in graphs of triangular grid, Doklady NASB, 49, 5, 21-25, (2005), (in Russian) · Zbl 1178.05057
[19] Orlovich, Yu.; Gordon, V.; Werner, F., Cyclic properties of triangular grid graphs, (), 149-153
[20] Plesnik, J., The NP-completeness of the Hamiltonian cycle problem in bipartite cubic planar graphs, Acta math. univ. Comenian., 42-43, 271-273, (1983) · Zbl 0539.05043
[21] Reay, J.R.; Zamfirescu, T., Hamiltonian cycles in \(T\)-graphs, Discrete comput. geom., 24, 497-502, (2000) · Zbl 0953.05040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.