PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.)
Vol. 56(70), pp. 23--33 (1994)
On the number of 2-factors in rectangular lattice graphs
Olga Bodroza-Panti\'c and Ratko Tos\'cInstitut za matematiku, Novi Sad, Yugoslavia
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:
Electronic fulltext finalized on: 1 Nov 2001. This page was last modified: 16 Nov 2001.
© 2001 Mathematical Institute of the Serbian Academy of Science and Arts