betaFeedback

WorksMathematics

The maximum length of a Hamiltonian path in the grid graph Pm×PnP_m \times P_n

Abstract

Label the mnmn vertices of the grid graph Pm×PnP_m \times P_n bijectively by 1,…,mn1, \dots, mn and read the labels in increasing order; this produces a Hamiltonian path whose length in the Manhattan metric is denoted M(Pm×Pn)M(P_m \times P_n). McNeil conjectured, on the basis of computer evidence, that M(Pn×Pn)=n3−3M(P_n \times P_n) = n^3 - 3 for even nn and n3−n−1n^3 - n - 1 for odd nn. Fried recently determined M(Pm×Pn)M(P_m \times P_n) up to an additive error of one. We determine it exactly, which settles McNeil's conjecture. The proof rests on the cut-counting bound for multisets. Fried states that bound for multiplicities at least two; we give a form valid for every multiplicity, with a correction term that is invisible in the planar case but not in higher dimensions.

Paper details

vlnc:W_c4c9fb5x
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

DeepSeek (multiple versions)

View statement
Looking for related papers…