ENUMERATION OF HAMILTONIAN CYCLES ON A THICK GRID CYLINDER - PART I: NON-CONTRACTIBLE HAMILTONIAN CYCLES

Applicable Analysis and Discrete Mathematics

article

Olga Bodroža-Pantić¹  Harris Kwong²  Rade Doroslovački³  Milan Pantić⁴ 

[1] Dept. of Math. & Info., Faculty of Science, University of Novi Sad;Dept. of Math. Sci.;Faculty of Technical Sciences, University of Novi Sad;Department of Physics, Faculty of Science, University of Novi Sad

关键词: Hamiltonian cycles;    Transfer matrix method;    generating functions;    thick grid cylinder;   

DOI  :  10.2298/AADM171215025B

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

In a recent paper, we have studied the enumeration of Hamiltonian cycles (abbreviated HCs) on the grid cylinder graph Pm+1 ×Cn, where m grows while n is fixed. Inthis sequel, we study a much harder problem of enumerating HCs on the same graphonly this time letting n grow while m is fixed. We propose a characterization fornon-contractible HCs which enables us to prove that their numbers hncm (n) satisfy arecurrence relation for every fixed m. From the computational data, we conjecture thatthe coefficient for the dominant positive characteristic root in the explicit formula forhncm (n) is 1.

【 授权许可】

Unknown