Filomat 2024 Volume 38, Issue 1, Pages: 57-65
https://doi.org/10.2298/FIL2401057D
Full text (
693 KB)
The structure of the 2-factor transfer digraph common for thin cylinder, torus and Klein bottle grid graphs
Đokić Jelena 
(Faculty of Technical Sciences, University of Novi Sad, Novi Sad, Serbia), jelenadjokic@uns.ac.rs
Doroslovački Ksenija (Faculty of Technical Sciences, University of Novi Sad, Novi Sad, Serbia), ksenija@uns.ac.rs
Bodroža-Pantić Olga (Dept. of Math. & Info., Faculty of Science, University of Novi Sad, Novi Sad, Serbia), olga.bodroza-pantic@dmi.uns.ac.rs
We prove that the transfer digraph D* C,m needed for the enumeration of
2-factors in the thin cylinder TnCm(n), torus TGm(n) and Klein bottle KBm(n)
(all grid graphs of the fixed width m and with m・n vertices), when m is
odd, has only two components of order 2m−1 which are isomorphic. When m is
even, D* C,m has [m/2] + 1 components which orders can be expressed via
binomial coefficients and all but one of the components are bipartite
digraphs. The proof is based on the application of recently obtained results
concerning the related transfer digraph for linear grid graphs (rectangular,
thick cylinder and Moebius strip).
Keywords: 2-factor, Hamiltonian cycles, transfer matrix, grid graphs
Show references
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), 028-060.
O. Bodroža-Pantić, H. Kwong, J. Đ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.
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:1(2015), 219-240.
J. des Cloizeaux, G. Jannik, Polymers in solution: Their modelling and structure, Clarendon Press, Oxford, 1990.
J. Đokić, O. Bodroža-Pantić and K. Doroslovački, A spanning union of cycles in rectangular grid graphs, thick grid cylinders and Moebius strips, Trans.Comb. (in press) (2023), http://dx.doi.org/10.22108/toc.2022.131614.1940, extended version (with Appendix) available at http://arxiv.org/abs/2109.12432, (2021), 1-95.
J. Đ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. (2023) OnLine-First, https://doi.org/10.2298/AADM211211006D.
J. Đokić, K. Doroslovački and O. Bodroža-Pantić, A spanning union of cycles in thin cylinder, torus and Klein bottle grid graphs, Mathematics, 11:4 (846)(2023), 1-20, extended version (with Appendix) available at http://arxiv.org/abs/2210.11527 (2022), 1-88.
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.
A. Kloczkowski, R.L. Jernigan, Transfer matrix method for enumeration and generation of compact self-avoiding walks. I. Square lattices, J. Chem. Phys. 109 (1998), 5134-46.
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:5 (2020), 1269-1282.
R. I. Nishat, S. Whitesides, Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs. Graph-theoretic Concepts in Computer Science 2019, 21(4), 325-337.
T.G. Schmalz, G.E. Hite, D.J. Klein, Compact self-avoiding circuits on two dimensional lattice, J. Phys. A: Math. Theor. 17 (1984), 445-453.
S. Singh, J. Lloyd and F. Flicker, Hamiltonian cycles on Ammann-Beenker Tilings, http://arxiv.org/abs/2302.01940, (2023), 1-19.
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.