This question is probably easy but I only have "tedious case checking" proof strategy in sight, and I'm sure there should be a reference lying around...


The question concerns the TSP problem (with fixed start- and end-vertex). The graph is the graph induced on the ball in an infinite grid. More precisely, the vertices are $B\_n = \lbrace (x,y) \in \mathbb{Z}^2 \mid |x|+|y| \leq n \rbrace$ and two vertices $v'=(x',y')$ and $v=(x,y)$ are neighbours if $|x-x'| +|y-y'|=1$.


$\textbf{Questions:}$ For two distinct vertices $v$ and $v'$ in $B\_n$ (say $n>2$) let $p\_{v,v'}$ be the shortest path between these vertices which goes at least once through any vertex. Let $|p|$ be the length of a path $p$.


* $\textbf{(1)}$ What is the smallest $k$ (possibly depending on $n$ but independent of $v$ and $v'$) such that $|p\_{v,v'}| \leq |B\_n| + k$? Can $k$ be chosen independently of $n$?
* $\textbf{(2)}$ What is the smallest $\ell$ (possibly depending on $n$) such that $\max\_{v,v'} |p\_{v,v'}| \leq \min\_{v,v'} |p\_{v,v'}|+\ell$? Can $\ell$ be chosen independently of $n$?


For rectangles (of sides $m \times n$) instead of balls, it is known that $k$ and $\ell$ can be chosen to be (respectively) $1$ and $2$ as soon as $m,n \geq 3$. I have the impression that this is sharp contrast to the case of a ball ($\ell$ might still be uniformly bounded but $k$ is probably $\simeq An+B$) 



Estimate for the travelling salesman problem for balls inside a grid
For question (1), $k$ grows linearly with $n$, so it cannot be chosen independently.


Color the vertices of the grid black and white, so that the vertices $(x,y)$ with $x+y$ even are black and the remaining vertices are white. Clearly, every edge of the graph has one end black and the other end white. Therefore, on every walk, the number of black and white vertices differs by at most one.


Now it is easy to see that $B\_n$ has $n^2$ vertices of one color and $(n+1)^2$ vertices of the other color. So every walk visiting all vertices of $B\_n$ has at least $|B\_n|+2n$ vertices, that is, at least $|B\_n|+2n-1$ edges. Now, if the two vertices $v$ and $v'$ belong to the minor color, then the length of the walk from $v$ to $v'$ must be at least $|B\_n|+2n+1$. 


The lower bound $|B\_n|+2n-1$ is achieved by a spiral-like walk that starts at $(0,n)$ and ends at $(0,0)$ for $n$ even, or $(1,0)$ for $n$ odd.


The case of arbitrary pair of endpoints remains to be solved. But clearly, $l$ is not larger than $2n+1$ (one can start with the spiral-like walk, perhaps rotated or reflected, and extend it to the required endpoints).


The existence of the spiral walk matching the necessary lower bound also implies that $k=l+2n-1$.


