×

zbMATH — the first resource for mathematics

Some new characterizations of Hamiltonian cycles in triangular grid graphs. (English) Zbl 1329.05176
Summary: In the studies that have been devoted to the protein folding problem, which is one of the great unsolved problems of science, some specific graphs, like the so-called triangular grid graphs, have been used as a simplified lattice model. Generation and enumeration of Hamiltonian paths and Hamiltonian circuits (compact conformations of a chain) are needed to investigate the thermodynamics of protein folding. In this paper, we present new characterizations of the Hamiltonian cycles in labeled triangular grid graphs, which are graphs constructed from rectangular grids by adding a diagonal to each cell. By using these characterizations and implementing the computational method outlined here, we confirm the existing data, and obtain some new results that have not been published. A new interpretation of Catalan numbers is also included.
MSC:
05C45 Eulerian and Hamiltonian graphs
05C30 Enumeration in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agarwala, R.; Batzoglou, S.; Dančik, V.; Decatur, S. E.; Hannenhalli, S.; Farach, M.; Muthukrishnan, S.; Skiena, S., Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model, J. Comput. Biol., 4, 3, 275-296, (1997) · Zbl 1321.92051
[2] Bodroža, O., An algorithm for generation and enumeration of Hamiltonian cycles in \(P_m \times P_n\), NSJOM, 24, 1, 261-267, (1994) · Zbl 0817.05043
[3] Bodroža-Pantić, O.; Kwong, H.; Pantić, M., A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs, Discrete Math. Theor. Comput. Sci., 17:1, 219-240, (2015) · Zbl 1311.05102
[4] Bodroža-Pantić, O.; Pantić, B.; Pantić, I.; Bodroža-Solarov, M., Enumeration of Hamiltonian cycles in some grid graphs, MATCH Commun. Math. Comput. Chem., 70:1, 181-204, (2013) · Zbl 1299.05203
[5] Bodroža-Pantić, O.; Tošić, R., On the number of 2-factors in rectangular lattice graphs, Publ. De L’Institut Math., 56, 70, 23-33, (1994) · Zbl 0831.05051
[6] Collins, K. L.; Krompart, L. B., The number of Hamiltonian paths in a rectangular grid, Discrete Math., 169, 29-38, (1997) · Zbl 0879.05035
[7] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of graphs — theory and application, (1982), VEB Deutscher Verlag der Wissenschaften Berlin
[8] des Cloizeaux, J.; Jannik, G., Polymers in solution: their modelling and structure, (1990), Clarendon Press Oxford
[9] Donaghey, R.; Shapiro, L. W., Motzkin numbers, J. Combin. Theory Ser. A, 23, 3, 291-301, (1977) · Zbl 0417.05007
[10] Faase, F. J., The number of specific spanning subgraphs of the graphs \(G \times P_n\), Ars Combin., 49, 129-154, (1998) · Zbl 0963.05065
[11] M.J. Golin, Y.C. Leung, Y. Wang, X. Yong, Counting structures in grid-graphs, cylinders and tori using transfer matrices: survey and new results (extended abstract), in: Proceedings of SIAM ALENEX/ANALCO Workshop-Analytic Algorithmics and Combinatorics (ANALCO05), Canada, Jan. 2005.
[12] Jacobsen, J. L., Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A, 40, 14667-14678, (2007) · Zbl 1135.82011
[13] Караваев, А.М., Кодирование состояний в методе матрицы переноса для подсчета гамилтоновых циклов на прямоуголных решетках, цилиндрах и торах, Информационные процессы, 11, 4, 476-499, (2011)
[14] A. Karavaev, S. Perepechko, Counting Hamiltonian cycles on triangular grid graphs, in: SIMULATION-2012, May 16-18, 2012, Kiev, http://www.flowproblem.ru/references.
[15] Kitchens, B. P., Symbolic dynamics, one-sided, two-sided and countable state Markov shifts, (1997), Springer
[16] Klazar, M., On \(a b a b\)-free and \(a b b a\)-free set partitions, European J. Combin., 17, 1, 53-68, (1996) · Zbl 0840.05004
[17] Kreweras, G., Dénombrement des cycles hamiltoniens dans un rectangle quadrillé, European J. Combin., 13, 6, (1992), 473-476 · Zbl 0762.05057
[18] Kwong, Y. H.H., Enumeration of Hamiltonian cycles in \(P_4 \times P_n\) and \(P_5 \times P_n\), Ars Combin., 33, 87-96, (1992)
[19] Kwong, Y. H.H.; Rogers, D. G., A matrix method for counting Hamiltonian cycles on grid graphs, European J. Combin., 15, 3, 277-283, (1994) · Zbl 0798.05032
[20] Peto, M.; Sen, T. Z.; Jernigan, R. L.; Kloczkowski, A., Generation and enumeration of compact conformations on the two-dimensional triangular and three-dimensional fcc lattices, J. Chem. Phys., 127, (2007), Article 044101
[21] Quaintance, J.; Kwong, H., A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13, #A29, (2013) · Zbl 1283.11047
[22] Stanley, R. P., Enumerative combinatorics, vol. I, (1986), Wadsworth & Brooks/Cole Monterey, CA · Zbl 0608.05001
[23] Stanley, R. P., Enumerative Combinatorics, vol. II, (2001), Cambridge University Press · Zbl 0978.05002
[24] Stanley, R. P., Catalan addendum to enumerative combinatorics, vol. 2, (2011), version 22 October
[25] Stoyan, R.; Strehl, V., Enumeration of Hamiltonian circuits in rectangular grids, J. Combin. Math. Combin. Comput., 21, 109-127, (1996) · Zbl 0857.05045
[26] Tošić, R.; Bodroža, O.; Kwong, Y. H.H.; Straight, H. J., On the number of Hamiltonian cycles of \(P_4 \times P_n\), Indian J. Pure Appl. Math., 21, 403-409, (1990) · Zbl 0736.05055
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.