论文标题
关于麦克尼尔的猜想
On a conjecture of McNeil
论文作者
论文摘要
假设将网格图的$ n^2 $顶点标记为标签，以便其标签的集合为$ \ {1,2，\ ldots，n^2 \} $。该标签在$ p_n^2 $上引起了步行，从标签为$ 1 $的顶点开始，该标签为$ 1 $，该顶点的标签为$ 2 $等，直到访问所有顶点。麦克尼尔（McNeil）研究了这种步行的最大可能长度的问题，当连续顶点之间的距离是曼哈顿距离时，麦克尼尔（McNeil在这项工作中，我们研究了$ p_m \ times p_n $的更一般情况，并捕获$ m（p_m \ times p_n）$，添加系数为$ 1 $。这特别是麦克尼尔猜想的值。
Suppose that the $n^2$ vertices of the grid graph $P_n^2$ are labeled, such that the set of their labels is $\{1,2,\ldots,n^2\}$. The labeling induces a walk on $P_n^2$, beginning with the vertex whose label is $1$, proceeding to the vertex whose label is $2$, etc., until all vertices are visited. The question of the maximal possible length of such a walk, denoted by $M(P_n^2)$, when the distance between consecutive vertices is the Manhattan distance, was studied by McNeil, who, based on empirical evidence, conjectured that $M(P_n^2)=n^3-3$, if $n$ is even, and $n^3-n-1$, otherwise. In this work we study the more general case of $P_m\times P_n$ and capture $M(P_m\times P_n)$, up to an additive factor of $1$. This holds, in particular, for the values conjectured by McNeil.
