Isometric path cover number of the 2 dimensional grid graph

Question

I am looking for a proof of the fact that at least $2n/3$ isometric paths (i.e. shortest paths between the end points) are required to cover the vertices of the $n\times n$ grid graph (i.e. Cartesian product of two path graphs).

I believe that this result is proved in the paper 'The isometric number of a graph' (J. Combin. Math. Combin. Comput. 38 (2001) 97-110) by S.L. Fitzpatrick and D.C. Fisher. Unfortunately, I could not find any access to this paper on the web. It would be greatly appreciated if someone who has a proof of this result (or, access to the paper) can share it here. Thanks.

Answer 1

I don't see how to prove $2n/3$ easily, but in case it is useful here is a simple idea in order to prove a lower bound of $(2-\sqrt{2})n> 0.58n$, beating the simple $n/2$ lower bound coming from diameter considerations.

You consider the induced subgraph $H$ of the $n$ by $n$ grid $G$ obtained by removing all vertices at distance at most $\alpha n$ from one of the 4 corners of the grid, for $0\le \alpha\le 1/2$. So $H$ has $(1-2\alpha^2+o(1))n^2$ vertices. Because $H$ is an isometric subgraph of $G$ and $H$ has diameter at most $(2-2\alpha)n$, any isometric path cover of $G$ requires at least $(1-2\alpha^2+o(1))n^2/(2-2\alpha)n$ paths. Taking $\alpha=1-1/\sqrt{2}$ we obtain the desired result.

Anyway the the best is probably to send an email to Shannon Fitzpatrick http://www.math.upei.ca/~sfitzpat/ and ask her if she could send you a copy of the original paper.

Answer 2

Assume you have $a$ increasing paths (where both coordinates non-strictly increase) and $b$ decreasing ones. We may assume that all of them start and finish at the vertices of the square.

Now perform an expanding of similar paths: if two increasing ones cross outside the regions $x+y<a+1$ and $x+y>2n-a+1$, you may modify one path so as to keep all points covered by the increasing paths still covered by them, but make the collection “wider”. Performing such procedure, we come to the collection where no paths of the same direction cross ourside the two triangles (and they cover the triangles).

Now it remains to count the covered points. Outside the triangles, the paths cover $a(2n-2a+1)$ and $b(2n-2b+1)$ points respectively, and now the total number of crossing points is exactly $ab$, so the total number of covered points is $$ n^2\leq a(a-1)+b(b-1)+a(2n-2a+1)+b(2n-2b+1)-ab =2n(a+b)-(a^2+ab+b^2)\leq 2nS-3S^2/4, $$ where $S=a+b$. This yields $S\geq 2n/3$.

I may expand the part about expanding, but I hope it is clear what is happening.