Skip to main content
added 174 characters in body
Source Link

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.

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.

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.

Source Link

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.