Geodesic
A Limit Conjecture on the Number of Hamiltonian Cycles on Thin Triangular Grid Cylinder Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 405-427.

Voir la notice de l'article provenant de la source Library of Science

We continue our research in the enumeration of Hamiltonian cycles (HCs) on thin cylinder grid graphs Cm × Pn+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 ≥ 2.
Keywords: contractible Hamiltonian cycles, generating functions, thin triangular grid cylinder graph 
@article{DMGT_2018_38_2_a5,
     author = {Bodro\v{z}a-Panti\'c, Olga and Kwong, Harris and Doroslova\v{c}ki, Rade and Panti\'c, Milan},
     title = {A {Limit} {Conjecture} on the {Number} of {Hamiltonian} {Cycles} on {Thin} {Triangular} {Grid} {Cylinder} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {405--427},
     publisher = {mathdoc},
     volume = {38},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a5/}
}
TY  - JOUR
AU  - Bodroža-Pantić, Olga
AU  - Kwong, Harris
AU  - Doroslovački, Rade
AU  - Pantić, Milan
TI  - A Limit Conjecture on the Number of Hamiltonian Cycles on Thin Triangular Grid Cylinder Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 405
EP  - 427
VL  - 38
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a5/
LA  - en
ID  - DMGT_2018_38_2_a5
ER  - 
%0 Journal Article
%A Bodroža-Pantić, Olga
%A Kwong, Harris
%A Doroslovački, Rade
%A Pantić, Milan
%T A Limit Conjecture on the Number of Hamiltonian Cycles on Thin Triangular Grid Cylinder Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 405-427
%V 38
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a5/
%G en
%F DMGT_2018_38_2_a5
Bodroža-Pantić, Olga; Kwong, Harris; Doroslovački, Rade; Pantić, Milan. A Limit Conjecture on the Number of Hamiltonian Cycles on Thin Triangular Grid Cylinder Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 405-427. http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a5/

[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.

[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.

[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 × Pn, Ars Combin. 49 (1998) 129–154.

[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

[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).

[12] B.P. Kitchens, Symbolic Dynamics: One-sided, Two-sided and Countable State Markov Shifts (Springer, 1997).

[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 P4 × Pn and P5 × Pn, 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

[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).

[19] R. Stoyan and V. Strehl, Enumeration of Hamiltonian circuits in rectangular grids, J. Combin. Math. Combin. Comput. 21 (1996) 109–127.

[20] R. Tošić, O. Bodroža, Y.H.H. Kwong and H.J. Straight, On the number of Hamiltonian cycles of P4 × Pn, Indian J. Pure Appl. Math. 21 (1990) 403–409.