zbMATH — the first resource for mathematics

A limit conjecture on the number of Hamiltonian cycles on thin triangular grid cylinder graphs. (English) Zbl 1390.05099
Summary: We continue our research in the enumeration of Hamiltonian cycles (HCs) on thin cylinder grid graphs \(C_m\times P_{n_+1}\) by studying a triangular variant of the problem. There are two types of HCs, distinguished by whether they wrap around the cylinder. Using two characterizations of these HCs, we prove that, for fixed \(m\), the number of HCs of both types satisfy some linear recurrence relations. For small \(m\), computational results reveal that the two numbers are asymptotically the same. We conjecture that this is true for all \(m\geq2\).
05C30 Enumeration in graph theory
05C38 Paths and cycles
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05A15 Exact enumeration problems, generating functions
Full Text: DOI
[1] O. Bodroža-Pantić, B. Pantić, I. Pantić and M. Bodroža-Solarov, Enumeration of Hamiltonian cycles in some grid graphs, MATCH Commun. Math. Comput. Chem. 70 (2013) 181-204. · Zbl 1299.05203
[2] O. Bodroža-Pantić, H. Kwong and M. Pantić, Some new characterizations of Hamiltonian cycles in triangular grid graphs, Discrete Appl. Math. 201 (2016) 1-13. doi:10.1016/j.dam.2015.07.028
[3] O. Bodroža-Pantić, H. Kwong and M. Pantić, A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs, Discrete Math. Theoret. Comput. Sci. 17 (2015) 219-240.
[4] O. Bodroža-Pantić and R. Tošić, On the number of 2-factors in rectangular lattice graphs, Publ. Inst. Math. (Beograd) (N.S.) 56 (1994) 23-33. · Zbl 0831.05051
[5] D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Application (VEB Deutscher Verlag der Wissenschaften, Berlin, 1982).
[6] F.J. Faase, On the number of specific spanning subgraphs of the graphs G×P_n, Ars Combin. 49 (1998) 129-154. · Zbl 0963.05065
[7] M.J. Golin, Y.C. Leung, Y. Wang and 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 (Canada, 2005), 250-258.
[8] J.L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A 40 (2007) 14667-14678. doi:10.1088/1751-8113/40/49/003
[9] I. Jensen, Self-avoiding walks and polygons on the triangular lattice, J. Stat. Mech. Theory Exp. (2004) P10008. doi:10.1088/1742-5468/2004/10/P10008 · Zbl 1073.82559
[10] A.M. Karavaev, Kodirovanie sostoyanĭi v metode matricy perenosa dlya podscheta gamil’tonovyh ciklov na pryamougol’nyh reshetkah, cilindrah i torah, Informacionnye Processy 11 (2011) 476-499 (in Russian).
[11] A. Karavaev and S. Perepechko, Counting Hamiltonian cycles on triangular grid graphs, IV International Conference (Kiev, 2012). · Zbl 1340.82002
[12] B.P. Kitchens, Symbolic Dynamics: One-sided, Two-sided and Countable State Markov Shifts (Springer, 1997). · Zbl 0892.58020
[13] G. Kreweras, Dénombrement des Cycles Hamiltoniens dans un Rectangle Quadrillé, European J. Combin. 13 (1992) 473-467. doi:10.1016/0195-6698(92)90005-K
[14] Y.H.H. Kwong, Enumeration of Hamiltonian cycles in P_4 × P_n and P_5 × P_n, Ars Combin. 33 (1992) 87-96.
[15] Y.H.H. Kwong and D.G. Rogers, A matrix method for counting Hamiltonian cycles on grid graphs, European J. Combin. 15 (1994) 277-283. doi:10.1006/eujc.1994.1031 · Zbl 0798.05032
[16] M. Peto, T.Z. Sen, R.L. Jernigan and A. Kloczkowski, Generation and enumeration of compact conformations on the two-dimensional triangular and three-dimensional fcc lattices, J. Chem. Phys. 127 (2007) Article 044101.
[17] T.G. Schmalz, G.E. Hite and D.J. Klein, Compact self-avoiding circuits on two dimensional lattice, J. Phys. A 17 (1984) 445-453. doi:10.1088/0305-4470/17/2/029
[18] R.P. Stanley, Enumerative Combinatorics, Vol. I (Cambridge University Press, Cambridge, 2002). · Zbl 0889.05001
[19] R. Stoyan and V. Strehl, Enumeration of Hamiltonian circuits in rectangular grids, J. Combin. Math. Combin. Comput. 21 (1996) 109-127. · Zbl 0857.05045
[20] R. Tošić, O. Bodroža, Y.H.H. Kwong and H.J. Straight, On the number of Hamiltonian cycles of P_4 × P_n, Indian J. Pure Appl. Math. 21 (1990) 403-409.
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.