The structure of the 2-factor transfer digraph common for thin cylinder, torus and Klein bottle grid graphs

被引:0
作者
Dokic, Jelena [1 ]
Doroslovacki, Ksenija [1 ]
Bodroza-Pantic, Olga [2 ]
机构
[1] Univ Novi Sad, Fac Tech Sci, Novi Sad, Serbia
[2] Univ Novi Sad, Fac Sci, Dept Math & Info, Novi Sad, Serbia
关键词
2-factor; Hamiltonian cycles; transfer matrix; grid graphs; HAMILTONIAN CYCLES; ENUMERATION; CIRCUITS; NUMBER; WALKS;
D O I
10.2298/FIL2401057D
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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 center dot 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 + 1 components which orders can be expressed via binomial coefficients and all but one of 2 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).
引用
收藏
页码:57 / 65
页数:9
相关论文
共 14 条