Parity-dependent asymptotic domination of contractible Hamiltonian cycles

Let hmc(n)h_m^c(n) and hmnc(n)h_m^{nc}(n) denote, respectively, the numbers of contractible and non-contractible Hamiltonian cycles in the grid cylinder graph Pm+1×CnP_{m+1}\times C_n, and let θm,c\theta_{m,c} and θm,nc\theta_{m,nc} be the corresponding positive dominant characteristic roots. Parity-dependent domination conjecture. For fixed mm and nn\to\infty,

h_m(n)=h_m^c(n)+h_m^{nc}(n)\sim\left\{\begin{array}{ll}a_{m,c}n\theta_{m,c}^n&\operatorname{if} $m$ is odd},\theta_{m,nc}^n&\operatorname{if} $m$ is even}. \end{array}\right.

This predicts that contractible Hamiltonian cycles asymptotically dominate when mm is odd, whereas non-contractible Hamiltonian cycles dominate when mm is even. The claim is motivated by computational data for m9m\leq9 and is presented as a conjecture for all mm.

Sources & referencesView supporting material

Primary source

Olga Bodroža-Pantić, Harris Kwong, Jelena Djokić, Rade Doroslovački and Milan Pantić, “Enumeration of Hamiltonian Cycles on a Thick Grid Cylinder – Part II: Contractible Hamiltonian Cycles”, arXiv:2109.07875 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.