On the number of 2-factors in rectangular lattice graphs

Olga Bodroza-Panti\'c and Ratko Tos\'c

Abstract: Let $f_m(n)$ and $h_m(n)$ denote the number of 2-factors and the number of connected 2-factors (Hamiltonian cycles) respectively in a $(m-1)\times(n-1)$ grid i.e., in the labelled graph $P_m\times P_n$. We show that for each fixed $m$ ($m>1$) the sequences $f_m=(f_m(2),f_m(3), \dots)$ and $h_m=(h_m(2),h_m(3),\dots)$ satisfy difference equations (linear, homogeneous, and with constant coefficients). Furthermore, a computational method is given for finding these difference equations together with the initial terms of the sequence. The generating functions of $f_m$ and $h_m$ are rational functions $\Cal F_m$ and $\Cal H_m$ respectively, and they are given explicitly for some values of $m$.

Classification (MSC2000): 05C70, 05C45

Full text of the article:

• Compressed PostScript file (70 kilobytes)
• PDF file (191 kilobytes)