A spanning union of cycles in rectangular grid graphs, thick grid cylinders and Moebius strips

Document Type : Research Paper

Authors

1 Department of Fundamentals Sciences, Faculty of Technical Sciences, University of Novi Sad, 21000, Novi Sad, Serbia

2 Department of Mathematics and Informatics, Faculty of Sciences, University of Novi Sad, Novi Sad, Serbia

Abstract

Motivated to find the answers to some of the questions that have occurred in recent papers dealing with Hamiltonian cycles (abbreviated HCs) in some special classes of grid graphs we started the investigation of spanning unions of cycles, the so-called 2-factors, in these graphs (as a generalizations of HCs). For all the three types of graphs from the title and for any integer $m \geq 2$ we propose an algorithm for obtaining a specially designed (transfer) digraph ${\cal D}^*_m$. The problem of enumeration of 2-factors is reduced to the problem of enumerating oriented walks in this digraph. Computational results we gathered for $m \leq 17$ reveal some interesting properties both for the digraphs ${\cal D}^*_m$ and for the sequences of numbers of 2-factors.
We prove some of them for arbitrary $m \geq 2$.

Keywords

Main Subjects

References

[1] O. Bodroža-Pantić, H. Kwong, R. Doroslovački and M. Pantić, Enumeration of Hamiltonian cycles on a thick grid cylinder—Part I: Non-contractible Hamiltonian cycles, Appl. Anal. Discrete Math., 13 (2019) 28–60.
[2] O. Bodroža-Pantić, H. Kwong, R. Doroslovački and M. Pantić, A limit conjecture on the number of Hamiltonian cycles on thin triangular grid cylinder graphs, Discuss. Math. Graph Theory, 38 (2018) 405–427.
[3] O. Bodroža-Pantić, H. Kwong, J.D̄okić, R. Doroslovački and M. Pantić, Enumeration of Hamiltonian cycles on a thick grid cylinder—Part II: Contractible Hamiltonian cycles, Appl. Anal. Discrete Math., 16 (2022) 246–287.
[4] O. Bodroža-Pantić, H. Kwong and M. Pantić, A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs, Discrete Math. Theor. Comput. Sci., 17 (2015) 219–240.
[5] 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.
[6] 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.
[7] R. A. Brualdi and D. M. Cvetković, A combinatorial approach to matrix theory and its applications, Discrete Mathe-matics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2009.
[8] D. M. Cvetković, M. Doob and H. Sachs, Spectra of graphs. Theory and application, Second edition, VEB Deutscher Verlag der Wissenschaften, Berlin, 1982.
[9] J. D̄okić, O. Bodroža-Pantić and K. Doroslovački, A spanning union of cycles in rectangular grid graphs, thick grid cylinders and Moebius strips (with Appendix), arXiv:2109.12432[math.co] (2021) 1–26.
[10] J. D̄okić, K. Doroslovački and O. Bodroža-Pantić, The structure of the 2-factor transfer digraph common for rectangular, thick cylinder and Moebius strip grid graphs, Appl. Anal. Discrete Math., arXiv:2212.00317[math.co] (2022) 1–16.
[11] I. G. Enting and I. Jensen, Exact enumerations, Polygons, polyominoes and polycubes, , Lecture Notes in Phys., 775, Springer, Dordrecht, 2009 143–179.
[12] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1990.
[13] J. L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A: Math. Theor., 40 (2007) 14667–14678.
[14] T. C. Liang, K. Chakrabarty and R. Karri, Programmable daisychaining of microelectrodes to secure bioassay IP in MEDA biochips, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 25 (2020) 1269–1282.
[15] A. M. Karavaev, Kodirovanie sostoyaniı̆ v metode matricy perenosa dlya podscheta gamil′ tonovyh ciklov na pryamougol′ nyh reshetkah, cilindrah i torah, Informacionnye Processy, 11 (2011) 476–499.
[16] A. Karavaev and S. Perepechko, Counting Hamiltonian cycles on triangular grid graphs, IV International Con-ference, SIMULATION-2012, https://web.archive.org/web/20161015205252/http://flowproblem.ru/references, Kiev, 2012.
[17] A. Kloczkowski and R. L. Jernigan, Transfer matrix method for enumeration and generation of compact self-avoiding walks. I., Square lattices., J. Chem. Phys., 109 (1998) 5134–5146.
[18] E. S. Krasko, I. N. Labutin and A. V. Omelchenko, The enumeration of labeled and unlabeled Hamiltonian cycles in complete k-partite graphs, J. Math. Sci. (N.Y.), 255 (2021) 71–87.
[19] W. Kocay and D. L. Kreher, Discrete mathematics and its applications - graphs, algorithms, and optimization, Second Edition-CRC Press LLC-Chapman and Hall-CRC, 2017
[20] J. A. Montoya, On the counting complexity of mathematical nanosciences, MATCH Commun. Math. Comput. Chem., 86 (2021) 453–488.
[21] R. I. Nishat and S. Whitesides, Reconfiguring Hamiltonian cycles in L-shaped grid graphs, Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci., Springer, Cham, (2019) 325–337.
[22] V. H. Pettersson, Enumerating Hamiltonian cycles, Electron. J. Combin., 21 (2014) 1–15.
[23] R. P. Stanley, Enumerative Combinatorics, I, Cambridge University Press, Wadsworth, Monterey, 2002.
[24] N. J. A. Sloane, he on-line encyclopedia of integer sequences, (OEIS), https://oeis.org/A082758.
[25] A. Vegi Kalamar, T. Žerak, D. Bokal, Counting hamiltonian cycles in 2-tiled graphs, Mathematics, 9 (2021) 1–27.

Files

Cited by

History

  • Receive Date: 24 November 2021
  • Revise Date: 03 December 2022
  • Accept Date: 10 December 2022
  • Published Online: 01 March 2024

Share

How to cite

Statistics