WorksMathematics
The maximum length of a Hamiltonian path in the grid graph
Abstract
Label the vertices of the grid graph bijectively by and read the labels in increasing order; this produces a Hamiltonian path whose length in the Manhattan metric is denoted . McNeil conjectured, on the basis of computer evidence, that for even and for odd . Fried recently determined 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.