%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                                                               %%
%% This is the mc_template.tex file for the mc document class.   %%
%% It is used to prepare s manuscript for Mathematical 			 %%
%% Communications journal.                                       %%
%%                                                               %%
%% The mc.cls class works only with a pdflatex engine.           %%
%% The file newmc.cls should be placed where LaTeX 			     %%
%% can find it, e.g. in the current working directory.		     %%
%%                                                               %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{mc}
%%===============================================================%%

%%===============================================================%%
%% Please add here your own packages, macros and enviroments.    %%
%% It is not necessary to include ams* and graphicx packages     %%
%% since they are automatically included by the mc class.        %%
%% Avoid defining your own environments and use the already      %%
%% defined ones (e.g.~theorem, lemma etc.)                       %%
%%===============================================================%%
%\usepackage{anyfontsize}
%\usepackage{url}
\usepackage{tikz}
\usetikzlibrary{arrows.meta} 
\usepackage[caption=false]{subfig} 

\newcommand{\TV}{\operatorname{TV}}
%%===============================================================%%

%%===============================================================%%
%% Journal info will be edited by the typesetter  %%
%% DO NOT CHANGE THIS PART			                 %%
%%===============================================================%%
\setcounter{page}{1}
\renewcommand\thisnumber{x}
\renewcommand\thisyear {2025}
\renewcommand\thismonth{xxx}
\renewcommand\thisvolume{30}
\renewcommand\datereceived{February 2, 2025}
\renewcommand\dateaccepted{October 6, 2025}
\renewcommand\doinum{10.1000/100}
%%===============================================================%%

%\makeatletter\def\Hy@Warning#1{}\makeatother

\begin{document}
%%===============================================================%%
%% TITLE                                                         %%
%% Please add the title with \title[Short title]{Title}          %%
%% Short title is a running head apearing in the header.         %%
%%===============================================================%%
\title[On a conjecture of McNeil]
{On a conjecture of McNeil} 
%%===============================================================%%

%%===============================================================%%
%% AUTHOR(S)                                                     %%
%%                                                               %%
%% Add author's details in the following format. For each author %%
%% provide the affiliation, address and Orcid identifier.		 %%
%% Mark the corresponding author with \comma\corrauth.			 %%
%%===============================================================%%
\author[S.~Fried]%
{Sela Fried\orcidnumber{0000-0002-1547-4925}}		 

\address{Department of Computer Science, Israel Academic College, 52275 Ramat Gan, Israel} 

\emailsingle{%
\email{friedsela@gmail.com}}
%%===============================================================%%

%%===============================================================%%
%% ABSTRACT                                                      %%
%%===============================================================%%
\begin{abstract}
We determine the maximum length of a walk on the grid graph $P_m \times P_n$, up to an additive error of $1$. This nearly settles McNeil's conjecture for the square grid graph $P_n \times P_n$.
\end{abstract}
%%===============================================================%%

%%===============================================================%%
%% KEYWORDS                                                      %%
%%===============================================================%%
\keywords{graph labeling; grid graph; Manhattan distance; permutation}
%%===============================================================%%

%%===============================================================%%
%% AMS subject classification                                    %%
%%===============================================================%%
\ams{05C12, 05A05, 05C78, 90C27}
%%===============================================================%%

%%===============================================================%%
\maketitle
%%===============================================================%%

%%===============================================================%%
%% MAIN BODY                                                     %%
%%===============================================================%%

\section{Introduction}

Let $m$ and $n$ be two positive integers and consider the grid graph $P_m\times P_n$. Assume that the $mn$ vertices of $P_m\times P_n$ are labeled bijectively by $\{1,2,\ldots,mn\}$. The labeling induces a walk on $P_m\times P_n$, beginning with the vertex labeled $1$, proceeding to the vertex labeled $2$, and so on, until finally the vertex labeled $mn$ is reached. This work is concerned with the following question: What is the maximum possible length of such a walk, denoted by $M(P_m\times P_n)$, if the distance between consecutive labeled vertices is the Manhattan distance? See Figure \ref{fig1} for a visualization.

\begin{figure}[ht]
\centering
\subfloat[]{%
\begin{tikzpicture}[scale=1]
  \coordinate (BL) at (0,0);
  \coordinate (BR) at (2,0);
  \coordinate (TL) at (0,2);
  \coordinate (TR) at (2,2);
  \draw[line width=0.5pt] (BL) rectangle (TR);
  \fill (TL) circle (2.5pt);
  \fill (TR) circle (2.5pt);
  \fill (BL) circle (2.5pt);
  \fill (BR) circle (2.5pt);
  \node[above left]  at (TL) {$1$};
  \node[above right] at (TR) {$2$};
  \node[below left]  at (BL) {$4$};
  \node[below right] at (BR) {$3$};
  \draw[thick, -Stealth, shorten <=3pt, shorten >=3pt] (TL) -- (TR);
  \draw[thick, -Stealth, shorten <=3pt, shorten >=3pt] (TR) -- (BR);
  \draw[thick, -Stealth, shorten <=3pt, shorten >=3pt] (BR) -- (BL);
\end{tikzpicture}%
}\hspace{1.2cm}%
\subfloat[]{%
\begin{tikzpicture}[scale=1]
  \coordinate (BL) at (0,0);
  \coordinate (BR) at (2,0);
  \coordinate (TL) at (0,2);
  \coordinate (TR) at (2,2);
  \draw[line width=0.5pt] (BL) rectangle (TR);
  \fill (TL) circle (2.5pt);
  \fill (TR) circle (2.5pt);
  \fill (BL) circle (2.5pt);
  \fill (BR) circle (2.5pt);
  \node[above left]  at (TL) {$1$};
  \node[above right] at (TR) {$3$};
  \node[below left]  at (BL) {$4$};
  \node[below right] at (BR) {$2$};
  \draw[thick, -Stealth, shorten <=3pt, shorten >=3pt] (TL) -- (BR);
  \draw[thick, -Stealth, shorten <=3pt, shorten >=3pt] (BR) -- (TR);
  \draw[thick, -Stealth, shorten <=3pt, shorten >=3pt] (TR) -- (BL);
\end{tikzpicture}%
}
\caption{Two walks on the grid graph $P_2\times P_2$. The left walk has length $3=1+1+1$, while the right walk has length $2+1+2=5$, which is maximal. Thus, $M(P_2\times P_2)=5$.}
\label{fig1}
\end{figure}


This question was studied in two special cases: the case $P_1\times P_n$ reduces to standard permutations since $P_1\times P_n$ is isomorphic to $P_n$. It was shown by Bulteau et al.\ \cite{B} that $M(P_n)=\lfloor n^2/2\rfloor -1$. The second case, with $m=n$, was studied by McNeil (see sequence A179094 in \cite{OL}). Based on empirical evidence, McNeil proposed the following conjecture.
\begin{conjecture}
Assume that $n\geq 2$. Then 
\[M(P_n\times P_n)=\begin{cases}n^3-3, &\textnormal{if $n$ is even},\\
n^3-n-1, & \textnormal{if $n$ is odd}.
\end{cases}\]
\end{conjecture}

Our results are summarized in the following theorem. In particular, they nearly settle McNeil's conjecture.

\begin{theorem}\label{ag1}
We have $M(P_2\times P_n)\in\{r,r+1\}$, where $r=(n+1)^2-4$. Furthermore, if $m,n\geq 3$, then:
\begin{enumerate}
\item[$1.$] If $m$ and $n$ are both even, then $M(P_m\times P_n)\in\{r,r+1\}$, where \[r=\frac{mn(m+n)}{2} - 3.\]
\item[$2.$] If $m$ and $n$ are both odd, then $M(P_m\times P_n)\in\{r,r+1\}$, where \[r=\frac{mn(m+n)}{2}-\frac{m+n}{2}-1.\]
\item[$3.$] If $m$ is odd and $n$ is even, then \[M(P_m\times P_n)=\frac{mn(m+n)}{2}-\frac{n}{2}-1.\] 
\end{enumerate} 
\end{theorem}

\section{Main results}

Throughout the paper, let $m,n\geq 2$ be two integers. We set $[n]=\{1,2,\ldots,n\}$ and identify the vertex set of $P_m\times P_n$ with $V=[m]\times[n]$. Thus, the labelings we consider are bijections $\sigma\colon V\to[mn]$. The Manhattan distance between two vertices $(i,j),(i',j')\in V$ is
\[d((i,j),(i',j')) = |i-i'|+|j-j'|.\] If $c$ is a condition, let $\mathbf{1}_c$ denote its indicator function, which is equal to $1$ if $c$ holds and $0$ otherwise. For two sequences $a,b$, we write $a\circ b$ for their concatenation. If $a=(a_1,\ldots,a_n)$ is a sequence, we denote by $\TV(a)$ the total variation of $a$, i.e., $\TV(a)=\sum_{i=1}^{n-1}|a_{i+1}-a_i|$. The proof of Theorem \ref{ag1} consists of an upper bound (Lemma \ref{l3}) and corresponding lower bounds (Lemmas \ref{222}, \ref{888}, \ref{889}, and \ref{8899}). 

\subsection{The upper bound}

A key ingredient in the proof of the upper bound (Lemma \ref{l3}) is an extension of the maximum total variation formula of Bulteau et al.\ \cite{B} from permutations ($m=1$) to permutations of a multiset consisting of $m\geq 2$ copies of $[n]$ (Lemma \ref{ga10}). The proof of this extension uses the following result concerning the maximum number of transitions in binary words.

\begin{lemma}\label{l10}
The maximum number of transitions from $0$ to $1$ or from $1$ to $0$ in a binary word of length $n$ with $k$ ones is
\[
2\min\{k,n-k\} -\mathbf{1}_{k= \frac{n}{2}}.
\]
\end{lemma}

\begin{proof}
Recall that a run in a binary word is a subword consisting of consecutive zeros or ones that is not preceded or followed by the same digit. It is well known (e.g., \cite[p.\ 52]{T}) that the maximum number of runs in a binary word of length $n$ with $k$ ones is
\[
2\min\{k,n-k\}+1 -\mathbf{1}_{k= \frac{n}{2}}.\] Since the number of transitions is equal to the number of runs minus one, the assertion follows.
\end{proof}

\begin{lemma}\label{ga10}
Denote by $S(m,n)$ the set of permutations of the elements of the multiset containing $m$ copies of $[n]$. Then 
\begin{equation}\label{e811}
\max_{\sigma\in S(m,n)}\TV(\sigma)=
2m\left\lfloor \frac{n}{2}\right\rfloor \left\lceil\frac{n}{2}\right\rceil-\mathbf{1}_{2|n}.
\end{equation}
\end{lemma}

\begin{proof}
For $\sigma=(\sigma_1,\ldots,\sigma_{mn})\in S(m,n)$ set 
\[C_k(\sigma)=\sum_{i=1}^{mn-1}\mathbf{1}_{\textnormal{$(\sigma_i\leq k<\sigma_{i+1})$ or $(\sigma_{i+1}\leq k<\sigma_i)$}}.\] We claim that 
\begin{equation}\label{e18a}
\TV(\sigma)=\sum_{k=1}^{n-1} C_k(\sigma).
\end{equation} Indeed, for $x,y\in[n]$ and $k\in [n-1]$, we have
\[|x-y|=\sum_{k=1}^{n-1}\mathbf{1}_{\textnormal{$(x\leq k<y)$ or $(y\leq k<x)$}}.\] Thus, 
\begin{align*}
\TV(\sigma) &= \sum_{i=1}^{mn-1}|\sigma_{i+1}-\sigma_i|\\  
&= \sum_{i=1}^{mn-1}\sum_{k=1}^{n-1}\mathbf{1}_{\textnormal{$(\sigma_i\leq k<\sigma_{i+1})$ or $(\sigma_{i+1}\leq k<\sigma_i)$}}\\
&=\sum_{k=1}^{n-1} C_k(\sigma).
\end{align*}

Now, let $p_k\colon S(m,n)\to \{0,1\}^{mn}$ be the projection defined as follows: For $i\in[mn]$, let the $i$th coordinate of $p_k(\sigma)$ be $\mathbf{1}_{\sigma_i\leq k}$. It follows that $C_k(\sigma)$ is equal to the number of transitions in $p_k(\sigma)$. Indeed,
\begin{align*}
C_k(\sigma)&= \sum_{i=1}^{mn-1}\mathbf{1}_{\textnormal{$(\sigma_i\leq k<\sigma_{i+1})$ or $(\sigma_{i+1}\leq k<\sigma_i)$}}\\
&=\sum_{i=1}^{mn-1}\mathbf{1}_{\textnormal{$((p_{k}(\sigma))_{i}=1\text{ and }(p_{k}(\sigma))_{i+1}=0)$ or $((p_{k}(\sigma))_{i}=0\text{ and }(p_{k}(\sigma))_{i+1}=1)$}}\\
&=\textnormal{number of transitions in $p_k(\sigma)$}.
\end{align*}

Applying Lemma \ref{l10} to the binary word $p_k(\sigma)$, which has length $mn$ and $mk$ ones, we conclude that 
\begin{equation}\label{e17}
C_k(\sigma) \leq 2m\min\{k,n-k\}-\mathbf{1}_{k=\frac{n}{2}}.
\end{equation}
Summing \eqref{e17} over $k\in[n-1]$ and using the identity
\[
\sum_{k=1}^{n-1}\min\{k,n-k\}
=\left\lfloor\frac {n}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil,
\] which may be found, for example, in sequence A002620 in \cite{OL}, together with $\sum_{k=1}^{n-1}\mathbf{1}_{k=\frac{n}{2}}=\mathbf{1}_{2|n}$, we conclude from \eqref{e18a} that
\[
\TV(\sigma) \leq 
2m\left\lfloor\frac{n}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil
-\mathbf{1}_{2|n}.
\] This proves that the left-hand side of \eqref{e811} is at most the right-hand side. To prove the equality, we shall construct a permutation that attains the upper bound. We distinguish between even and odd $n$. Assume first that $n$ is odd, i.e., $n=2k+1$ for some integer $k\geq 1$. For $j\in[k]$, define a sequence $B_{j, m, n}$ of length $2m$ by \[B_{j, m, n} =(j, n+1-j,\ j, n+1-j,\ \ldots,\ j, n+1-j).\] Now define $\sigma$ as follows: 
\[\sigma=(k+1)\circ B_{1,m,n}\circ\cdots \circ B_{k,m,n} \circ (\underbrace{k+1, \ldots, k+1}_{\textnormal{$m-1$ times}}).\] To calculate $\TV(\sigma)$, notice that $\TV(B_{j,m,n})=(2m-1)(n+1-2j)$. Furthermore, for $j\in[k-1]$, the absolute difference between the last element of $B_{j,m,n}$ and the first element of $B_{j+1,m,n}$ is $n-2j$. It follows that 
\begin{align*}
\TV(\sigma)&=|k+1-1|+\sum_{j=1}^k(2m-1)(n+1-2j)+\sum_{j=1}^{k-1}(n-2j)+|n+1-k-(k+1)|\\
&=2mk(n-k)\\
&=2m\left\lfloor \frac{n}{2}\right\rfloor \left\lceil\frac{n}{2}\right\rceil.
\end{align*}

Assume now that $n$ is even, i.e., $n=2k$ for some integer $k\geq 1$. For $j\in[k]$ define a sequence $B_{j, m, n}$ of length $2m$ by \[B_{j, m, n} =(n+1-j,j,\ n+1-j, j,\ \ldots,\ n+1-j,j).\] Now define $\sigma$ in two steps: First, let \[\sigma'= B_{1,m,n}\circ\cdots \circ B_{k,m,n}.\] Then let $\sigma$ be the sequence obtained from $\sigma'$ by cutting its last element (which is $k$) and inserting it at the beginning of $\sigma'$. As in the odd case, $\TV(B_{j,m,n})=(2m-1)(n+1-2j)$, and, for $j\in[k-1]$, the absolute difference between the last element of $B_{j,m,n}$ and the first element of $B_{j+1,m,n}$ is $n-2j$. It follows that 
\begin{align*}
\TV(\sigma)&=|k-n|+\sum_{j=1}^k(2m-1)(n+1-2j)+\sum_{j=1}^{k-1}(n-2j)-1\\
&=2mk(n-k)-1\\
&=2m\left\lfloor \frac{n}{2}\right\rfloor \left\lceil\frac{n}{2}\right\rceil-1. 
\end{align*}

Thus, in both cases there is a permutation attaining the upper bound and the proof is complete.
\end{proof}

We may now prove the upper bound on $M(P_m\times P_n)$.

\begin{lemma}\label{l3}
We have \[M(P_m\times P_n) \leq 2n\left\lfloor \frac{m}{2}\right\rfloor \left\lceil\frac{m}{2}\right\rceil-\mathbf{1}_{2|m}+2m\left\lfloor \frac{n}{2}\right\rfloor \left\lceil\frac{n}{2}\right\rceil-\mathbf{1}_{2|n}.\]
\end{lemma}

\begin{proof}
Consider a labeling $\sigma$ of $P_m\times P_n$, i.e., $\sigma\colon V\to [mn]$ is a bijection. For $t\in[mn]$, write $(i_t,j_t)=\sigma^{-1}(t)$ and notice that the multiset $\{i_t\;:\;t\in[mn]\}$ is equal to $n$ copies of $[m]$ and the multiset $\{j_t\;:\;t\in[mn]\}$ is equal to $m$ copies of $[n]$. Thus, by Lemma \ref{ga10}, 
\begin{align}
\sum_{t=1}^{mn-1} d( \sigma^{-1}(t),\sigma^{-1}(t+1))&=\sum_{t=1}^{mn-1} |i_{t+1}-i_t|+\sum_{t=1}^{mn-1} |j_{t+1}-j_t|\nonumber\\&\leq 2n\left\lfloor \frac{m}{2}\right\rfloor \left\lceil\frac{m}{2}\right\rceil-\mathbf{1}_{2|m}+2m\left\lfloor \frac{n}{2}\right\rfloor \left\lceil\frac{n}{2}\right\rceil-\mathbf{1}_{2|n}.\nonumber\qedhere
\end{align}
\end{proof}

\subsection{The lower bound}

The proof of the lower bound consists of four constructions, which, taken together, cover all cases listed in Theorem \ref{ag1}.

\begin{lemma}\label{222}
Assume that $n$ is odd. Then $M(P_2\times P_n)\geq (n+1)^2-4$.
\end{lemma}

\begin{proof}
Let $\sigma\colon V\to [2n]$ be the bijection given by \[\left[\begin{array}{ccccccccc}
n-1 & \cdots & 4 & 2 & n+1 & 2n & n+3 & \cdots & 2n-2\\
2n-1 & \cdots & n+4 & n+2 & 1 & 3 & 5 & \cdots & n
\end{array}\right].\] The walk $1\to 2\to \cdots\to n$ has length $\sum_{i=1}^{n-1}(i+1)$. Now, $\frac{n+1}{2}$ steps lead to $n+1$ and additional $2$ steps to $n+2$. Then, a walk of length $\sum_{i=3}^{n-1}(i+1)$ leads to $2n-1$. Finally, $\frac{n+3}{2}$ steps lead to $2n$ and the walk is completed with a total length of $(n+1)^2 -4$.
\end{proof}

\begin{lemma}\label{888}
Assume that $m$ and $n$ are both even. Then
\[
M(P_m\times P_n)\geq \frac{mn(m+n)}{2} - 3.\]
\end{lemma}

\begin{proof}
Let $r=\frac{mn}{2}$ and let $\sigma\colon V\to [mn]$ be the bijection given by
\[\left[
\begin{array}{cccc|cccc}
r-1 & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & mn-1\\
\vdots &  &  & \vdots & \vdots &  &  & \vdots\\
\cdots & \cdots & 3 & 1 & r+1 & r+3 & \cdots & \cdots\\\hline
\cdots & \cdots & \cdots & mn & r & \cdots & \cdots & \cdots\\
\vdots &  &  & \vdots & \vdots &  &  & \vdots\\
r+2 & r+4 & \cdots &\cdots & \cdots & \cdots & 4 & 2
\end{array}\right].\]
First, we describe the bijection explicitly. The array of size $m\times n$ is divided into four regions, each of size $\frac{m}{2}\times\frac{n}{2}$. The labels are distributed as follows: 
\begin{enumerate}
\item The top-left region contains the odd labels $1,3,\ldots,r-1$ arranged so that $1$ is at index $(\frac{m}{2},\frac{n}{2})$ and each row is strictly increasing from right to left and each column is strictly increasing from bottom to top.
\item The top-right region contains the odd labels $r+1,r+3,\ldots,mn-1$ arranged so that $r+1$ is at index $(\frac{m}{2},\frac{n}{2}+1)$ and each row is strictly increasing from left to right and each column is strictly increasing from bottom to top.
\item The bottom-right region contains the even labels $2,4,\ldots,r$ arranged so that $2$ is at index $(m, n)$ and each row is strictly increasing from right to left and each column is strictly increasing from bottom to top.
\item The bottom-left region contains the even labels $r+2,\ldots,mn$ arranged so that $r+2$ is at index $(m, 1)$ and each row is strictly increasing from left to right and each column is strictly increasing from bottom to top.
\end{enumerate} We split $\sum_{t=1}^{mn-1} d(\sigma^{-1}(t),\sigma^{-1}(t+1))$ into its horizontal and vertical parts. 
\begin{enumerate}
\item Horizontal part - There are $\frac{mn}{4}$ walks from the top-left region to the bottom-right region, each has length $\frac{n}{2}$. The return walks have length $\frac{n+2}{2}$, except those that go from column $\frac{n+2}{2}$. These have length $1$, with the exception of the walk from $r$ to $r+1$ which has no horizontal part. By symmetry, the walks between the other pair of diagonal regions contribute exactly the same distance. It follows that the total horizontal contribution is 
\[2\left(\frac{mn^2}{8} +\left(\frac{mn}{4} - \frac{m}{2}\right)\frac{n+2}{2} + \frac{m}{2} - 1\right)=\frac{mn^{2}}{2}-2.\]
\item Vertical part - There are $\frac{mn}{4}$ walks from the top-left region to the bottom-right region, each has length $\frac{m}{2}$. The walks back are also of length $\frac{m}{2}$, except those that go from column $\frac{n+2}{2}$. These have length $\frac{m+2}{2}$, with the exception of the walk from $r$ to $r+1$ which has length $1$. By symmetry, the walks between the other pair of diagonal regions contribute exactly the same distance, except that we halt at label $mn$. It follows that the total vertical contribution is \[2\left(\frac{m^2n}{8} +\left(\frac{mn}{4} - \frac{m}{2}\right)\frac{m}{2} + \frac{m-2}{2}\cdot\frac{m+2}{2}+1\right) - 1=\frac{m^2n}{2}-1.\]
\end{enumerate} Combining the two parts yields a total distance of
\[\frac{mn^{2}}{2}-2+\frac{m^2n}{2}-1=\frac{mn(m+n)}{2}-3,\] as asserted.
\end{proof}

\begin{lemma}\label{889}
Assume that $m,n\geq 3$ are both odd. Then 
\[
M(P_m\times P_n)\geq\frac{mn(m+n)}{2}-\frac{m+n}{2}-1.\]
\end{lemma}

\begin{proof}
Let $r=\frac{(m+1)(n-1)}{2}$ and let $\sigma\colon V\to [mn]$ be the bijection given by
\[\left[
\begin{array}{cccc|c|cccc}
r-1&\cdots&\cdots&\cdots&r+1&mn-2&\cdots&\cdots&\cdots\\
\vdots&&&\vdots &\vdots&\vdots&&&\vdots\\
\vdots&&&\vdots&r+m-2&\cdots&\cdots&r+m+2&r+m\\
\cline{5-9}
\cdots&\cdots&3&1&mn&r&\cdots&\cdots&\cdots\\\cline{1-5}
mn-1&\cdots&\cdots&\cdots&r+2&\vdots&&&\vdots\\
\vdots&&&\vdots&\vdots&\vdots&&&\vdots\\
\cdots&\cdots&r+m+3&r+m+1&r+m-1&\cdots&\cdots&4&2
\end{array}\right].\]
First, we describe the bijection explicitly. The array of size $m\times n$ is divided into seven regions and the labels are distributed as follows:
\begin{enumerate}
\item The top-left region contains the odd labels $1,3,\ldots,r-1$ arranged so that $1$ is at index $(\frac{m+1}{2},\frac{n}{2})$ and each row is strictly increasing from right to left and each column is strictly increasing from bottom to top.
\item The top-middle region contains the odd labels $r+1,\ldots,r+m-2$ one above the other, arranged so that $r+1$ is in the first row and each row is strictly increasing from top to bottom.
\item The top-right region contains the odd labels $r+m,r+m+2,\ldots,mn-2$ arranged so that $r+m$ is at index $(\frac{m-1}{2},n)$ and each row is strictly increasing from right to left and each column is strictly increasing from bottom to top.
\item The bottom-right region contains the even labels $2,4,\ldots,r$ and is defined similarly to the top-left region.
\item The bottom-middle region contains the even labels $r+2,\ldots,r+m-1$ and is defined similarly to the top-middle region.
\item The bottom-left region contains the even labels $r+m+1,r+m+3,\ldots,mn-1$ and is defined similarly to the top-right region.
\item The central region consists only of the label $mn$ at index $(\frac{m+1}{2},\frac{n+1}{2})$. 
\end{enumerate} We split $\sum_{t=1}^{mn-1} d(\sigma^{-1}(t),\sigma^{-1}(t+1))$ into its horizontal and vertical parts. 
\begin{enumerate}
\item Horizontal part - There are $\frac{(m+1)(n-1)}{4}$ walks from the top-left region to the bottom-right region, each has length $\frac{n+1}{2}$. The return walks have length $\frac{n+3}{2}$, except those that go from column $\frac{n+3}{2}$. These have length $2$, with the exception of the walk from $r$ to $r+1$, which has length $1$. Next, the walk $r+1\to r+2\to\cdots\to r+m-1$ has no horizontal part. Thus, we continue from $r+m-1$. Moving to $r+m$ gives $\frac{n-1}{2}$. Now, there are $\frac{(m-1)(n-1)}{4}$ walks from the top-right region to the bottom-left region, each has length $\frac{n+1}{2}$. The return walks have length $\frac{n-1}{2}$, except those that go from the first column. These have length $n-1$, with the exception of the walk from $mn-1$ to $mn$, which has length $\frac{n-1}{2}$. It follows that the total horizontal contribution is 
\begin{align*}
&\frac{(m+1)(n^2-1)}{8} + \left(\frac{(m+1)(n-1)}{4} - \frac{m+1}{2}\right) \frac{n+3}{2} + 2\cdot\frac{m-1}{2} + 1+ \frac{n-1}{2}\\&+\frac{(m-1)(n^2-1)}{8} + \left(\frac{(m-1)(n-1)}{4} - \frac{m-1}{2}\right)\frac{n-1}{2}+ \left(\frac{m-1}{2}-1\right)(n-1) +\frac{n-1}{2}\\
= &\, \frac{mn^{2}-m}{2}-1.
\end{align*}
\item Vertical part - There are $\frac{(m+1)(n-1)}{4}$ walks from the top-left region to the bottom-right region, each has length $\frac{m-1}{2}$. The return walks have length $\frac{m-1}{2}$, except those that go from column $\frac{n+1}{2}+1$. These have length $\frac{m+1}{2}$, with the exception of the walk from $r$ to $r+1$, which has length $\frac{m-1}{2}$. Now, there are $\frac{m-1}{2}$ walks from the top-middle region to the bottom-middle region, all having length $\frac{m+1}{2}$. The return walks have length $\frac{m-1}{2}$, except the last one from $r+m-1$ to $r+m$, which has length $\frac{m+1}{2}$. Now, there are $\frac{(m-1)(n-1)}{4}$ walks from the top-right region to the bottom-left region, each has length $\frac{m+1}{2}$. The return walks also have length $\frac{m+1}{2}$, except those that go from the first column. These have length $\frac{m+3}{2}$, with the exception of the walk from $mn-1$ to $mn$, which has length $1$. It follows that the total vertical distance is 
\begin{align*}
&\frac{(m^2-1)(n-1)}{8} + \left(\frac{(m+1)(n-1)}{4} - \frac{m+1}{2}\right)\frac{m-1}{2} + \frac{m-1}{2}\cdot\frac{m+1}{2}\\
&+ \frac{m-1}{2}+\frac{m-1}{2}\cdot\frac{m+1}{2}+\frac{m-3}{2}\cdot\frac{m-1}{2}+\frac{m+1}{2}+\frac{(m^2-1)(n-1)}{8}\\
&+ \left(\frac{(m-1)(n-1)}{4} - \frac{m-1}{2}\right)\frac{m+1}{2}+\frac{m-3}{2}\cdot\frac{m+3}{2} +1\\
= &\,\frac{m^{2}n-n}{2}.
\end{align*}
\end{enumerate} Combining the two parts yields a total distance of
\[\frac{mn^{2}-m}{2}-1+\frac{m^{2}n-n}{2}=\frac{mn(m+n)}{2}-\frac{m+n}{2}-1,\] as asserted.
\end{proof}

\begin{lemma}\label{8899}
Assume that $m\geq 3$ is odd and $n\geq 3$ is even. Then 
\[
M(P_m\times P_n)\geq \frac{mn(m+n)}{2}-\frac{n}{2}-1.\]
\end{lemma}

\begin{proof}
Set $r=\frac{(m+1)n}{2}-3$ and let $\sigma\colon V\to [mn]$ be the bijection given by
\[\left[
\begin{array}{cccc|cccc}
r &\cdots  &  &\cdots  &  \cdots&  \cdots& r+5 &r+3\\
\vdots &  & & \vdots & \vdots &  &  & \vdots\\
\vdots &  &  & \vdots&  mn-2&\cdots  &\cdots & \cdots \\\cline{6-8}\cline{0-0}
\multicolumn{1}{c|}{mn-1} & \cdots & 3 & 1 & \multicolumn{1}{c|}{mn} & r+1 &\cdots  & \cdots\\\cline{2-5}
mn-3 & \cdots&\cdots & \cdots & \vdots &  &  &\vdots \\
\vdots &  &  & \vdots & \vdots &  & & \vdots\\
\cdots &\cdots  &r+4  &r+2 & \cdots & \cdots & 4 &2
\end{array}\right].\]
First, we describe the bijection explicitly. The array of size $m\times n$ is divided into four regions and the labels are distributed as follows:
\begin{enumerate}
\item The top-left region is a rectangular array of size $\frac{m+1}{2}\times\frac{n}{2}$ missing its bottom-left cell. It contains the odd labels $1,3,\ldots,r$ arranged so that $1$ is at index $(\frac{m+1}{2},\frac{n}{2})$ and each row is strictly increasing from right to left and each column is strictly increasing from bottom to top.
\item The top-right region is a rectangular array of size $\frac{m-1}{2}\times\frac{n}{2}$ to which an additional cell is attached beneath its bottom-left cell. It contains the even labels $r+3,r+5,\ldots,mn$ arranged so that $r+3$ is at index $(1,n)$ and each row is strictly increasing from right to left and each column is strictly increasing from top to bottom.
\item The bottom-right region is a rectangular array of size $\frac{m+1}{2}\times\frac{n}{2}$ missing its top-left cell. It contains the even labels $2,4,\ldots,r+1$ arranged so that $2$ is at index $(m,n)$ and each row is strictly increasing from right to left and each column is strictly increasing from bottom to top.
\item The bottom-left region is a rectangular array of size $\frac{m-1}{2}\times\frac{n}{2}$ to which an additional cell is attached above its top-left cell. It contains the odd labels $r+2,r+4,\ldots,mn-1$ arranged so that $r+2$ is at index $(m,\frac{n}{2})$ and each row is strictly increasing from right to left and each column is strictly increasing from bottom to top.
\end{enumerate} We split $\sum_{t=1}^{mn-1} d(\sigma^{-1}(t),\sigma^{-1}(t+1))$ into its horizontal and vertical parts. 
\begin{enumerate}
\item Horizontal part - The first $\frac{n-2}{2}$ walks from the top-left region to the bottom-right region have length $\frac{n}{2}$. The next walk is only $1$ step long. Now come $\frac{n-2}{2}$ walks having length $\frac{n+2}{2}$. This pattern of $1 + \frac{n-2}{2}\cdot\frac{n+2}{2}$ repeats $\frac{m-1}{2}$ times. Now consider the return walks. At the beginning, there are $\frac{n-4}{2}$ walks having length $\frac{n+2}{2}$. Now come two walks of length $2$, followed by $\frac{n-4}{2}$ walks having length $\frac{n+4}{2}$. This pattern of $2\cdot 2 + \frac{n-4}{2}\cdot\frac{n+4}{2}$ repeats $\frac{m-1}{2}$ times. At this point we arrive at $r+1$, and two steps bring us to $r+2$. All $\frac{m-1}{2}\cdot\frac{n}{2}+1$ walks from the bottom-left region to the top-right region have length $\frac{n}{2}$. The walks back follow the pattern of $\frac{n-2}{2}$ walks having length $\frac{n+2}{2}$ and then one step. This pattern repeats $\frac{m-1}{2}$ times, except that the very last walk has length $\frac{n}{2}$, instead of $1$. It follows that the total horizontal contribution is 
\begin{align*}
&\frac{n-2}{2}\cdot\frac{n}{2}+\left(1+\frac{n-2}{2}\cdot\frac{n+2}{2}\right)\frac{m-1}{2}+	
\frac{n-4}{2}\cdot\frac{n+2}{2}+\left(2\cdot2+\frac{n-4}{2}\cdot\frac{n+4}{2}\right)\frac{m-1}{2}\\
&+	2 + \left(\frac{m-1}{2}\cdot\frac{n}{2}+1\right)\frac{n}{2}+\left(\frac{n-2}{2}\cdot\frac{n+2}{2}+1\right)\frac{m-1}{2}-1+\frac{n}{2}\\
=&\,\frac{mn^2}{2}-1.
\end{align*}
\item Vertical part - The first $\frac{n-2}{2}$ walks from the top-left region to the bottom-right region have length $\frac{m-1}{2}$. The next walk has length $\frac{m+1}{2}$. This pattern repeats $\frac{m+1}{2}$ times, except the very last step. Now consider the return walks. There are $\frac{n-4}{2}$ walks having length $\frac{m-1}{2}$, followed by two walks having length $\frac{m+1}{2}$. This pattern repeats $\frac{m+1}{2}$ times, except the very last two steps. At this point we arrive at $r+1$ and $\frac{m-1}{2}$ steps bring us to $r+2$. The walks from the bottom-left region to the top-right region follow this rule: For each $i\in\left[\frac{m-1}{2}\right]$, there are $\frac{n}{2}$ walks having length $m+1-2i$. Similarly, the walks back follow this rule: For each $i\in\left[\frac{m-1}{2}\right]$, there are $\frac{n-2}{2}$ walks having length $m+1-2i$ and one of length $m-2i$. This brings us to $mn-1$. The walk to $mn$ has no vertical part. It follows that the total vertical contribution is 
\begin{align*}
&\left(\frac{n-2}{2}\cdot\frac{m-1}{2}+\frac{m+1}{2}\right)\frac{m+1}{2}-\frac{m+1}{2}+	
\left(\frac{n-4}{2}\cdot\frac{m-1}{2}+2\cdot\frac{m+1}{2}\right)\frac{m+1}{2}\\
&-2\cdot\frac{m+1}{2}+\frac{m-1}{2}+	
\sum_{i=1}^{\frac{m-1}{2}}\frac{n}{2}(m+1-2i)+\sum_{i=1}^{\frac{m-1}{2}}\left(\frac{n-2}{2}(m+1-2i)+(m-2i)\right)	 \\
=&\,\frac{n(m^2-1)}{2}.
\end{align*}
\end{enumerate} Combining the two parts yields a total distance of
\[\frac{mn^2}{2}-1+\frac{n(m^2-1)}{2}=\frac{mn(m+n)}{2}-\frac{n}{2}-1,\] as asserted.
\end{proof}

\section{Conclusion}

It is natural to ask what happens if we consider graphs different from the grid graph. To make it more concrete, suppose $G$ is a graph of order $n$ with vertex set $V$. The distance between two vertices $x,y\in V$, denoted by $d(x,y)$, is the length of a shortest path along the edges of $G$ joining $x$ and $y$. Set 
\[\Sigma=\{\sigma\colon V\to [n]\;:\;\textnormal{$\sigma$ is a bijection}\}.\] Then define
\[M(G) =\max_{\sigma\in \Sigma}\sum_{i=1}^{n-1}d(\sigma^{-1}(i), \sigma^{-1}(i+1)).\] We propose to call $M(G)$ the \emph{disorder number of $G$}, echoing the name \emph{additive $y$-disorder} used in \cite{B}.

\begin{example}
Dominus \cite{Dom} proved that \[M(Q_n)=(2^{n-1}-1)(2n-1)+n,\] where $Q_n$ is the hypercube graph with $2^n$ vertices. See also sequence A271771 in \cite{OL}.
\end{example}

To our knowledge, the cycle graph $C_n$ has not been studied in this regard. We obtain the following result. See also sequence A000982 in \cite{OL}.

\begin{theorem}
For $n\geq 3$, we have \[
M(C_n)=\left\lceil \frac{(n-1)^2}{2}\right\rceil.
\]
\end{theorem}

\begin{proof}
Identify the vertices of $C_n$ with the set $[n]$. The distance $d(x,y)$ between two vertices $x,y\in[n]$ is then $\min\{|x-y|,n-|x-y|\}$. We distinguish between two cases. 
\begin{enumerate}
    \item $n$ is even. There are $\frac{n}{2}$ pairs of vertices $x,y\in[n]$ with $d(x,y)=\frac{n}{2}$. The remaining $\frac{n-2}{2}$ steps therefore have length at most $\frac{n-2}{2}$. Thus,
    \[M(C_n)\leq \left(\frac{n}{2}\right)^{2}+\left(\frac{n-2}{2}\right)^{2}=\frac{(n-1)^{2}+1}{2}.\] On the other hand, the bijection $[n]\to[n]$ given by
    \[\left[1, \frac{n}{2}+1, 2, \frac{n}{2}+2, \ldots, \frac{n}{2}, n\right]\] obviously attains the upper bound.
    \item $n$ is odd. The maximum distance between any two vertices is $\frac{n-1}{2}$. Thus,
    \[M(C_n)\leq (n-1)\frac{n-1}{2}.\] On the other hand, with $k=\frac{n-1}{2}$ and interpreting the residue $0$ as $n$, the bijection $[n]\to[n]$ given by
    \[[1, 1+k, 1+2k,\ldots,1+(n-1)k]\ (\bmod\ n)\] obviously attains the upper bound. \qedhere
\end{enumerate}
\end{proof}

\begin{remark}
The Manhattan distance used in this work is induced by the $\ell_1$ norm. It is natural to ask what happens if we replace it by a distance induced by another norm $||\cdot||$ on $\mathbb{R}^2$ (e.g., the Euclidean norm $||\cdot||_2$). Let $\Sigma$ be the set of bijections $\sigma\colon V\to[mn]$. Then one may consider
\[
M_{||\cdot||}(P_m\times P_n)=\max_{\sigma\in\Sigma}\sum_{t=1}^{mn-1}||\sigma^{-1}(t+1)-\sigma^{-1}(t)||.
\] This seems interesting and may require methods different from those used in this work.
\end{remark}

%%===============================================================%%
%% ACKNOWLEDGEMENTS                                              %%
%% Acknowledgements can be added here.                           %%
%%===============================================================%%
\section*{Acknowledgements}
The author would like to thank the referees for their careful reading of the manuscript and for their helpful suggestions.

%%===============================================================%%
%% REFERENCES                                                    %%
%% References should be provided in bibtex file.                 %%
%% We suggest using MR Lookup for finding bibtex entries.        %%
%%===============================================================%%
\bibliography{references}

\end{document}