# Strong edge geodetic problem on grids

Eva Zmazek

###### Abstract

Let $G=(V(G),E(G))$ be a simple graph. A set $S\subseteq V(G)$ is a strong
edge geodetic set if there exists an assignment of exactly one shortest path
between each pair of vertices from $S$, such that these shortest paths cover
all the edges $E(G)$. The cardinality of a smallest strong edge geodetic set
is the strong edge geodetic number $\operatorname{\rm sg_{e}}(G)$ of $G$. In
this paper, the strong edge geodetic problem is studied on the Cartesian
product of two paths. The exact value of the strong edge geodetic number is
computed for $P_{n}\,\square\,P_{2}$, $P_{n}\,\square\,P_{3}$ and
$P_{n}\,\square\,P_{4}$. Some general upper bounds for $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{m})$ are also proved.

Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

<EMAIL_ADDRESS>
Keywords: strong geodetic problem; strong edge geodetic problem; Cartesian
product of paths

AMS Subj. Class.: 05C12, 05C70

##  1 Introduction

Different covering problems with shortest paths were studied in literature.
For example, the geodetic problem was introduced in $1993$ in [3] and its edge
version in $2007$ in [11]. In $2016$, the strong geodetic problem was
introduced, the seminal paper [9] being published only recently. Since then, a
lot of work was done on the strong geodetic problem.

The exact value of the strong geodetic number was computed for different
families of graphs. For example, for complete bipartite graphs $K_{n,m}$ it
was first computed for cases when $n=m$, and for $n\gg m$ in [4], and later in
the general case in [1]. In [6], the strong geodetic number was computed for
some balanced multipartite complete graphs and it was shown that computing the
strong geodetic number of general complete multipartite graphs is NP-complete.
The exact strong geodetic number was also computed for crown graphs
$S_{0}^{n}$ in [1], Hamming graphs $K_{m}\,\square\,K_{n}$ in [5], Cartesian
products $K_{1,n}\,\square\,P_{l}$ in [5], thin ($n\gg m$) grids
$P_{n}\,\square\,P_{m}$, and thin ($n\gg m$) cylinders $P_{n}\,\square\,C_{m}$
in [7], and $i$-level complete Appolonian networks $A(i)$ in [9].

Several general bounds on the strong geodetic number were given using
different graphical invariants. In [4], bounds on $\operatorname{\rm
sg_{e}}(G)$ were given depending on the diameter $\operatorname{\rm diam}(G)$
of $G$. In [12], an upper bound on the strong geodetic number was given using
the connectivity number. In [9], lower and upper bounds were given using
isometric path number. Gledel at al. [2] proved an upper bound on the strong
geodetic number of Cartesian product graphs using the so-called strong
geodetic core number. In [1], an upper bound on the strong edge geodetic
number was given for hypercubes. A general upper bound was in [5] computed for
the strong geodetic number of Cartesian product graphs and an upper bound for
the strong geodetic number of the Cartesian product of a path with an
arbitrary graph was computed in [7].

Using reduction from NP-completeness of dominating set problem, Manuel et al.
in [9] proved that the strong geodetic problem is NP-complete. On the positive
side Mezzini in [10] gave a polynomial algorithm for computing the strong
geodetic number of outerplanar graphs. Some general properties about the
strong geodetic number were also given. For example, in [12] the graphs with
the strong geodetic number $2$, $n(G)$, or $n(G)-1$, were charactarized. In
[5] relation between the strong geodetic number of a graph and its induced,
convex, or gated subgraphs were derived.

Like geodetic problem and many other problems in graph theory, there is an
interesting edge version of the problem. In $2017$, the edge version of the
strong geodetic problem, called the strong edge geodetic problem, was
introduced in [8], but it did not get as much attention as the vertex version.
This gap is in part filled in this paper. In the seminal paper [8] it was
proved that the strong edge geodetic problem is NP-complete and some general
upper and lower bound were given using the isometric path number, the number
of simplicial vertices in a graph, and the number of convex components in
graph. In this article, we will show that even though the vertex and edge
version of the strong geodetic problem seem similar at the first sign, they
differ a lot. For example, in [7] it was proved that if $2\leq n\leq m$, then
$\operatorname{\rm sg}(P_{n}\,\square\,P_{m})\leq\left\lceil
2\sqrt{n}~{}\right\rceil$, while we will prove that this is not true for the
strong edge geodetic number $\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{m})$
when $m=3$ or $4$. The main results of this article are the following three
theorems.

######  Theorem 1.1.

If $n\geq 2$, then $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{2})=\left\lceil 2\sqrt{n}~{}\right\rceil$.

######  Theorem 1.2.

If $n\geq 2$, then $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{3})=\left\lceil 2\sqrt{n+1}~{}\right\rceil$.

######  Theorem 1.3.

If $n\geq 2$, then

$\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{4})=\begin{cases}2k+1;&n=k^{2}+h,0\leq h\leq
k-1,\\\ 2k+2;&n=k^{2}+h,k\leq h\leq 2k-1,\\\ 2k+3;&n=k^{2}+2k.\end{cases}$

Theorem 1.3 implies that $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{4})=\left\lceil 2\sqrt{n+2}~{}\right\rceil$ for all
$n\in\mathbb{N}$ except when $n=k^{2}+k-1$ for some $k\in\mathbb{N}$. This can
also be interpreted as $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{4})=\left\lceil 2\sqrt{n+1}~{}\right\rceil$ for all
$n\in\mathbb{N}$ except when $n=k^{2}+2k$ for some $k\in\mathbb{N}$. This
shows that the pattern from Theorems 1.1 and 1.2 does not extend to $n\geq 4$.

In the next section we formally define concepts needed in this paper and
prepare several preliminary results. Then, in Sections 3-5, we prove Theorems
1.1, 1.2, 1.3, respectively. In the last section we give three general upper
bounds on $\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{m})$.

##  2 Preliminaries

Let $G=(V(G),E(G))$ be a simple graph. A $x,y$-geodesic is a shortest path
between vertices $x$ and $y$. With $P(G;x,y)$ we denote the set of all
shortest paths in $G$ between vertices $x$ and $y$. A set $S\subseteq V(G)$ is
a _strong edge geodetic set_ if there exists an assignment of shortest paths
$P_{x,y}\in P(G;x,y)$ for every pair $x,y\in V(G)$, such that

$\bigcup\limits_{\\{x,y\\}\in\binom{S}{2}}E(P_{x,y})=E(G),$

where $E(P_{x,y})$ denotes the set of edges from the selected shortest path
$P_{x,y}$. The set of these shortest paths is called the _strong edge
covering_. The _strong edge geodetic number_ of $G$, denoted by
$\operatorname{\rm sg_{e}}(G)$, is the cardinality of a smallest strong edge
geodetic set of $G$.

_The Cartesian product_ $G\,\square\,H$ of graphs $G$ and $H$ is the graph on
the vertex set $V(G\,\square\,H)=V(G)\times V(H)$, where two vertices
$(g_{1},h_{1})$ and $(g_{2},h_{2})$, $g_{1},g_{2}\in V(G)$, $h_{1},h_{2}\in
V(H)$ are adjecent if $g_{1}g_{2}\in E(G)$ and $h_{1}=h_{2}$, or if
$g_{1}=g_{2}$ and $h_{1}h_{2}\in E(H)$. An edge $(g_{1},h_{1})(g_{2},h_{2})\in
E(G\,\square\,H)$ is said to be _horizontal_ if $h_{1}=h_{2}$ and is said to
be _vertical_ if $g_{1}=g_{2}$. A _grid_ is the Cartesian product of two
paths. The _$i$ -th row_, $1\leq i\leq m$, in $P_{n}\,\square\,P_{m}$ is the
vertex set $\\{(1,i),\dots,(n,i)\\}$ together with the horizontal edges
between them. Similarly, the _$j$ -th column_, $1\leq j\leq n$, in
$P_{n}\,\square\,P_{m}$ is the vertex set $\\{(j,1),\dots,(j,m)\\}$ together
with the vertical edges between them. Because of the commutativity of the
Cartesian product operation, $\operatorname{\rm
sg_{e}}(G\,\square\,H)=\operatorname{\rm sg_{e}}(H\,\square\,G)$. A subgraph
$H$ of a graph $G$ is _convex_ if for every pair of vertices $\\{x,y\\}$ in
$H$, every $x,y$-geodesic lies completely in $H$. A set of edges $F\subseteq
E(G)$ is a _convex edge-cut_ if $G-F$ has precisely two convex components.

######  Lemma 2.1.

If $n\geq 2$ and $m\geq 2$, then $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{m})\geq\left\lceil 2\sqrt{n}~{}\right\rceil$.

###### Proof.

In [8, Corollary 6.4] it is proved that if $F$ is a convex edge-cut of a graph
$G$, then $\operatorname{\rm sg_{e}}(G)\geq\lceil 2\sqrt{|F|}\rceil.$ In our
case, all vertical edges between the first and the second row in
$P_{n}\,\square\,P_{m}$ represent a convex edge-cut set of
$P_{n}\,\square\,P_{m}$ (see Fig. 1). Because there are exactly $n$ vertical
edges between the first and the second row in $P_{n}\,\square\,P_{2}$, the
inequality holds.

⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮ Figure 1: Edge-cut in $P_{n}\,\square\,P_{m}$.

∎

Throughout the rest of this paper, we will use Algorithm 1 to prove upper
bounds on the strong edge geodetic number. The input of this algorithm are an
integer $n$ and an integer $m$. Integer $n$ can be uniquely written as the sum
$n=k^{2}+h$, where $k$ and $h$ are integers and $0\leq h\leq 2k$. Algorithm
defines a set of vertices $S$ and a set of shortest paths, where for each pair
of vertices in $S$ it uses at most one shortest path between them, such that
the union of this shortest paths covers all the vertical edges in
$P_{n}\,\square\,P_{m}$.

Algorithm 1 first takes two vertices, $a_{1}=(1,1)$ and $b_{1}=(1,m)$ from the
first column, and cover the vertical edges in the first column by the unique
$a_{1},b_{1}$-geodesic. In next step, if $k^{2}\geq 4$, the algorithm takes
vertices $a_{2}=(2^{2},1)$ and $b_{2}=(2^{2},m)$ and covers the second column
of edges by the $a_{1}$,$b_{2}$-geodesic, the third column of edges by the
$a_{2},b_{1}$-geodesic and the fourth column of edges by the
$a_{2},b_{2}$-geodesic. After the $(i-1)$-th, $(i-1)^{2}\leq n$, step, all the
first $(i-1)^{2}$ columns are already covered. In the $i$-th step, if
$i^{2}\leq n$, we add vertices $a_{i}=(i^{2},1)$ and $b_{i}=(i^{2},m)$. We
cover the next $i-1$ columns by $a_{1},b_{i}$-, …, $a_{i-1},b_{i}$-geodesic,
respectively the way every geodesics covers the leftmost not yet covered
column of edges. Similarly, we cover $i-1$ edges from the
$(i-1)^{2}+(i-1)+1$-th to the $(i-1)^{2}+2(i-1)$-th column by $a_{i},b_{1}$-,
…, $a_{i},b_{i-1}$-geodesic, respectively, covering the leftmost not yet
covered column of edges. The algorithm covers the $i$-th column of edges by
the unique $a_{i},b_{i}$-geodesic. This way we cover all the vertical edges
from the first $k^{2}$ columns.

If $1\leq h\leq k$, we add the vertex $b_{k+1}=(n,m)$ and then cover the
remaining columns of edges by $a_{1},b_{k+1}$-, …, $a_{h},b_{k+1}$-geodesic,
respectively, covering the leftmost not yet covered column of edges. If
$k+1\leq h\leq 2k$, we add vertices $a_{k+1}=(n,1)$ and $b_{k+1}=(n,m)$. We
cover the next $k$ columns by $a_{1},b_{k+1}$-, …, $a_{k},b_{k+1}$-geodesic,
respectively, the way every geodesics covers the leftmost not yet covered
column of edges. Simirarly, we cover the remaining columns of edges by
$a_{k+1},b_{1}$-, …, $a_{k+1},b_{h-k}$-geodesic, respectively, covering the
leftmost not yet covered column of edges.

Input: integer $n=k^{2}+h$, where $0\leq h\leq 2k$, and integer $m$

Result: strong edge geodetic set and a set of shortest paths in
$P_{n}\,\square\,P_{m}$, $m\geq 2$, that cover all vertical edges

1 for  _$i=1,\dots,k$_ do

2 $a_{i}=\left(i^{2},1\right)$;

3 $b_{i}=\left(i^{2},m\right)$;

4 for  _$j=1,\dots,i-1$_ do

5 connect vertices $a_{i}$ and $b_{j}$ with a geodesic that covers all
vertical edges in $((i-1)^{2}+j)$-th column of $P_{n}\,\square\,P_{m}$

6 end for

7 for  _$j=1,\dots,i-1$_ do

8 connect vertices $a_{j}$ and $b_{i}$ with a geodesic that covers all
vertical edges in $(i(i-1)+j)$-th column of $P_{n}\,\square\,P_{m}$

9 end for

10 connect vertices $a_{i}$ and $b_{i}$ with the unique geodesic between them

11 end for

12if  _$1\leq h\leq k$_ then

13 $b_{k+1}=\left(n,m\right)$;

14 for  _$j=1,\dots,h$_ do

15 connect vertices $a_{j}$ and $b_{k+1}$ with a geodesic that covers all
vertical edges in $(k^{2}+j)$-th column of $P_{n}\,\square\,P_{m}$

16 end for

17

18 end if

19else if  _$k+1\leq h\leq 2k$_ then

20 $a_{k+1}=\left(n,1\right)$;

21 $b_{k+1}=\left(n,m\right)$;

22 for  _$j=1,\dots,k$_ do

23 connect vertices $a_{j}$ and $b_{k+1}$ with a geodesic that covers all
vertical edges in $(k^{2}+j)$-th column of $P_{n}\,\square\,P_{m}$

24 end for

25 for  _$j=1,\dots,h-k$_ do

26 connect vertices $a_{k+1}$ and $b_{j}$ with a geodesic that covers all
vertical edges in $(k(k+1)+j)$-th column of $P_{n}\,\square\,P_{m}$

27 end for

28

29 end if

Algorithm 1 Covering vertical edges in grids

We conclude the preliminaries with the following technical lemma to be used in
our proofs.

######  Lemma 2.2.

$\left\lceil
2\sqrt{n\phantom{!}}\right\rceil=\begin{cases}2k;&n=k^{2},~{}k\in\mathbb{N},\\\
2k+1;&n=k^{2}+h,~{}k\in\mathbb{N},1\leq h\leq k,\\\
2k+2;&n=k^{2}+h,~{}k\in\mathbb{N},k+1\leq h\leq 2k.\end{cases}$

###### Proof.

If $n=k^{2}$ for some $k\in\mathbb{N}$, then $\left\lceil
2\sqrt{n\phantom{!}}\right\rceil=\left\lceil 2\sqrt{k^{2}}\right\rceil=2k$.

Suppose $n=k^{2}+h$ for some $k,h\in\mathbb{N}$ where $1\leq h\leq k$. Then
because $h>0$ and $\left\lceil 2\sqrt{k^{2}}\right\rceil$ is an integer, it
holds

$\left\lceil 2\sqrt{n\phantom{!}}\right\rceil=\left\lceil
2\sqrt{k^{2}+h}\right\rceil>\left\lceil 2\sqrt{k^{2}}\right\rceil=2k.$

Also, because $h\leq k$ and $\left\lceil 2\sqrt{k^{2}}\right\rceil$ is an
integer, it holds

$\left\lceil 2\sqrt{n\phantom{!}}\right\rceil\leq\left\lceil
2\sqrt{k^{2}+k}\right\rceil=\left\lceil
2\sqrt{(k^{2}+1/2)^{2}-1/4}\right\rceil\leq\left\lceil
2\sqrt{(k+1/2)^{2}}\right\rceil=2k+1.$

Because $\left\lceil 2\sqrt{n}~{}\right\rceil$ is an integer greater than $2k$
and is also less or equal to $2k+1$, we conclude that $\left\lceil
2\sqrt{n}~{}\right\rceil=2k+1$ when $n=k^{2}+h$, $1\leq h\leq k$.

Now suppose that $n=k^{2}+h$ for some $k,h\in\mathbb{N}$ where $k+1\leq h\leq
2k$. Then because $h\geq k+1$ and $\left\lceil
2\sqrt{(k+1/2)^{2}}\right\rceil$ is an integer, it holds

$\left\lceil 2\sqrt{n\phantom{!}}\right\rceil\geq\left\lceil
2\sqrt{k^{2}+k+1}\right\rceil=\left\lceil
2\sqrt{(k+1/2)^{2}+3/4}\right\rceil>\left\lceil
2\sqrt{(k+1/2)^{2}}\right\rceil=2k+1.$

Also, because $h\leq 2k$ and $\left\lceil 2\sqrt{k^{2}}\right\rceil$ is an
integer, it holds

$\left\lceil 2\sqrt{n\phantom{!}}\right\rceil\leq\left\lceil
2\sqrt{k^{2}+2k}\right\rceil\leq\left\lceil
2\sqrt{k^{2}+2k+1}\right\rceil=2k+2.$

Because $\left\lceil 2\sqrt{n}~{}\right\rceil$ is an integer greater than
$2k+1$ and is also less or equal to $2k+2$, we get $\left\lceil
2\sqrt{n}~{}\right\rceil=2k+2$ when $n=k^{2}+h$, $k+1\leq h\leq 2k$. ∎

##  3 Proof of Theorem 1.1

The lower bound $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{2})\geq\left\lceil 2\sqrt{n}~{}\right\rceil$
follows from Lemma 2.1. It remains to prove the upper bound $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{2})\leq\left\lceil 2\sqrt{n}~{}\right\rceil$.

We will use Algorithm 1 for $m=2$ to cover all the vertical edges in
$P_{n}\,\square\,P_{2}$. When $n=k^{2}$ for some $k\in\mathbb{N}$, the number
of vertices used in Algorithm 1 is exactly $2k$, these are the vertices
$a_{1},\dots,a_{k},b_{1},\dots,b_{k}$. When $n=k^{2}+h$, $k\in\mathbb{N}$,
$1\leq h\leq k$, the number of vertices used in Algorithm 1 is exactly $2k+1$,
and when $n=k^{2}+h$, $k\in\mathbb{N}$, $k+1\leq h\leq 2k$, exactly $2k+1$
vertices are used. By Lemma 2.2, we see that Algorithm 1 uses exactly $\lceil
2\sqrt{n}~{}\rceil$ vertices.

It remains to cover the horizontal edges. Observe that Algorithm 1 uses only
the $a_{j_{1}}$,$b_{j_{2}}$-geodesics for some $j_{1},j_{2}\in\mathbb{N}$.

If $n=k^{2}$, all horizontal edges from the first row can be covered by the
unique $a_{1}$,$a_{k}$-geodesic. Similarly, all horizontal edges from the
second row can be covered by the unique $b_{1}$,$b_{k}$-geodesic.

If $n=k^{2}+h$, where $1\leq h\leq k$, we can cover the horizontal edges in
the first row with the unique $a_{1}$,$a_{k}$-geodesic. The remaining
horizontal edges in the first row are already covered with the shortest path
from Algorithm 1 that covers vertical edges in the $n$-th column. We can cover
the horizontal edges from the second row with the unique
$b_{1}$,$b_{k+1}$-geodesic.

If $n=k^{2}+h$, where $k+1\leq h\leq 2k$, we can cover the horizontal edges
from the first row with the unique $a_{1}$,$a_{k+1}$-geodesic, and the
horizontal edges from the second row with the unique
$b_{1}$,$b_{k+1}$-geodesic.

This proves Theorem 1.1. See Fig. 2 for some typical optimal strong edge
geodetic sets in $P_{n}\,\square\,P_{2}$.

Figure 2: Strong edge geodetic set for graphs $P_{16}\,\square\,P_{2}$,
$P_{20}\,\square\,P_{2}$ and $P_{24}\,\square\,P_{2}$.

##  4 Proof of Theorem 1.2

We first show:

######  Lemma 4.1.

If $n\geq 2$, then $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{3})\leq\left\lceil 2\sqrt{n}~{}\right\rceil+1$.

###### Proof.

Use Algorithm 1 and then cover horizontal edges in the first row and in the
last row in the same way as in the proof of Theorem 1.1. Add vertex $(n,2)$ to
the existing vertex set from Algorithm 1, and connect it with $(1,1)$ by a
geodesic that covers all horizontal edges from the second row, see Fig. 3. ∎

Figure 3: Shortest path between $(1,1)$ and $(n,2)$.

By Lemma 4.1 and Lemma 2.1 (for $m=3$) we know that for every $n\geq 2$, the
strong edge goedetic number $\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{3})$
is either $\left\lceil 2\sqrt{n}~{}\right\rceil$ or $\left\lceil
2\sqrt{n}~{}\right\rceil+1$. Because by Lemma 2.2 it holds $\left\lceil
2\sqrt{n}~{}\right\rceil=\left\lceil 2\sqrt{n+1}~{}\right\rceil$, except when
$n=k^{2}$ or $n=k^{2}+k$ for some $k\in\mathbb{N}$, it is enough to prove that
when $n=k^{2}$ or $n=k^{2}+k$, there is no strong edge geodetic set of size
$\left\lceil 2\sqrt{n}~{}\right\rceil$ and to find a strong edge geodetic set
of size $\left\lceil 2\sqrt{n}~{}\right\rceil$ in the other cases.

First, let us show that there exists a strong edge geodetic set of size
$\left\lceil 2\sqrt{n}~{}\right\rceil$ on $P_{n}\,\square\,P_{3}$ for
$n=k^{2}+h$, where $1\leq h\leq k-1$ or $k+1\leq h\leq 2k$.

######  Proposition 4.2.

If $n=k^{2}+h$, $n\geq 3$, $k\geq 1$, where $1\leq h\leq k-1$ or $k+1\leq
h\leq 2k$, then

$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{3})\leq\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{2}).$

###### Proof.

To cover all the vertical edges and all the horizontal edges in the second
row, we will adjust Algorithm 1. We will divide this adjustment into two
cases.

######  Case 1:

$n=k^{2}+h$, $1\leq h\leq k-1$ (see Fig. 4).
We can see that in this case, because $h\leq k-1$, Algorithm 1 never uses a
$a_{k}$,$b_{k+1}$-geodesic and that a $a_{1}$,$b_{k+1}$-geodesic covers all
vertical edges in the $(k^{2}+1)$-th column. Because $a_{k}=(k^{2},1)$, we can
add a $a_{k}$,$b_{k+1}$-geodesic that covers all the vertical edges in the
$(k^{2}+1)$-th column and then replace the existing $a_{1}$,$b_{k+1}$-geodesic
with the one that covers all the horizontal edges in the second row. This way
we have covered all the vertical edges in $P_{n}\,\square\,P_{3}$ and also all
the horizontal edges in the second row.

In the same way as in $P_{n}\,\square\,P_{2}$ we can cover the horizontal
edges in the first row (using the $a_{1}$,$a_{k}$-geodesic and also the
existing $a_{h}$,$b_{k+1}$-geodesic) and in the third row (using the
$b_{1}$,$b_{k+1}$-geodesic) of $P_{n}\,\square\,P_{3}$.

| $\to$ |
---|---|---

Figure 4: Strong edge geodetic set in $P_{3^{2}+2}\,\square\,P_{3}$.

######  Case 2:

$n=k^{2}+h$, $k+1\leq h\leq 2k$ (see Fig. 5).
In this case Algorithm 1 does not use the $a_{k+1}$,$b_{k+1}$-geodesic. This
shortest path covers all the vertical edges in the $n$-th column. Because a
$a_{k+1}$,$b_{h}$-geodesic from Algorithm 1 also covers all the vertical edges
from the $n$-th column, we can add a $a_{k+1}$,$b_{k+1}$-geodesic and then
replace an existing $a_{k+1}$,$b_{h}$-geodesic with the one that covers all
the vertical edges in the $(k^{2}+1)$-th column. This way we can then similar
to the previous case replace the existing $a_{1}$,$b_{k+1}$-geodesic (which
covers all the vertical edges in the $(k^{2}+1)$-th column in Algorithm 1)
with the one that covers all the horizontal edges in the second row of
$P_{n}\,\square\,P_{3}$.

In the same way as in $P_{n}\,\square\,P_{2}$ we now cover the horizontal
edges in the first row (using the $a_{1}$,$a_{k+1}$-geodesic) and in the third
row (using the $b_{1}$,$b_{k+1}$-geodesic) of $P_{n}\,\square\,P_{3}$.

| $\to$ |
---|---|---

| $\to$ |
---|---|---

Figure 5: Strong edge geodetic set in $P_{3^{2}+2\cdot 3}\,\square\,P_{3}$.

In both cases we have adjusted Algorithm 1 such that all the vertical edges
together with all the horizontal edges are covered without changing the set of
vertices used in the algorithm. It follows that $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{3})\leq\left\lceil
2\sqrt{n}~{}\right\rceil=\left\lceil 2\sqrt{n+1}~{}\right\rceil$ for all
$n\in\mathbb{N}$ when $n\not=k^{2}$ or $n\not=k^{2}+k$ for some
$k\in\mathbb{N}$. ∎

In the second part of the proof we will prove that there is no strong edge
geodetic set of size $\left\lceil 2\sqrt{n}~{}\right\rceil$ if $n=k^{2}$ or
$n=k^{2}+k$.

######  Proposition 4.3.

If $n=k^{2}$ or $n=k^{2}+k$ for some $k\geq 2$, $k\in\mathbb{N}$, then

$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{3})>\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{2}).$

###### Proof.

Let us define the function

$f_{s}(a,b,c)=ab+bc+2ac$

which gives an upper bound on how many different vertical edges can be covered
with shortest paths between $s$ vertices, where $a$ vertices lie in the first
row, $b$ vertices in the second row, and $c$ vertices in the third row in
$P_{n}\,\square\,P_{3}$, and for each pair of these vertices we use at most
one shortest path. The extremes of $f_{s}$ can be obtained by computer. For
example, if $a\geq 0$, $b\geq 0$, and $c\geq 0$, $a,b,c\in\mathbb{R}$, then
the maximum of $f_{s}$ is equal to $s^{2}/2$ and if $a\geq 0$, $b\geq 1$, and
$c\geq 0$, $a,b,c\in\mathbb{R}$, then the maximum of $f_{s}$ is equal to
$(s^{2}-1)/2$. We prove Proposition 4.3 by assuming the opposite in each case.

######  Case 1:

$n=k^{2}$.
Suppose that there exists a strong edge geodetic set $S$ in
$P_{n}\,\square\,P_{3}$ with $2k$ elements. If this set contains a vertex from
the second row (in which case $b\geq 1$), $f_{s}(a,b,c)$ is at most
$(s^{2}-1)/2$, which is in our case (when $s=2k$) equal to $(4k^{2}-1)/2$.
This is less than the number $2k^{2}$ of all the vertical edges in
$P_{n}\,\square\,P_{2}$, which in turn means that if there exists such a
strong edge geodetic set, then all the vertices from it are in the first and
the third row ($b=0$).

Now consider the edge $(1,2)(2,2)$. A shortest path that covers this edge has
to have one endpoint at $(1,1)$ or $(1,3)$, which means that at least one of
these vertices is in $S$. Without lost of generality we can assume that it has
one endpoint at $(1,1)$ (Fig. 6a). This shortest path then also covers the
edge $(1,1)(1,2)$. If $(1,3)\in S$, then the edge $(1,1)(1,2)$ is also covered
with the unique $(1,1)$,$(1,3)$-geodesic (Fig. 6b). Otherwise, the shortest
path that covers the edge $(1,2)(1,3)$ also covers the edge $(1,1)(1,2)$ (Fig.
6c). In both ways the edge $(1,1)(1,2)$ is covered at least twice, which means
that with the set of $2k$ vertices we can only find shortest paths between
them that cover at most $\max(f_{2k}-1)\leq 2k^{2}-1$ different vertical edges
which is again less that the number $2k^{2}$ of all the vertical edges in
$P_{n}\,\square\,P_{2}$. This implies that such a strong edge geodetic set $S$
cannot exist.

……… |  |  ……… |  |  ………
---|---|---|---|---
a |  | b |  | c
Figure 6: Covering the edge $(1,2)(2,2)$ in $P_{n}\,\square\,P_{3}$ when
$n=k^{2}$.

######  Case 2:

$n=k^{2}+k$.
Suppose that there exist a strong edge geodetic set $S$ of
$P_{n}\,\square\,P_{3}$ with $2k+1$ elements. If this set does not include a
vertex $(1,2)$, we can similarly as in the previous case without loss of
generality conclude that the edge $(1,1)(1,2)$ is covered at least twice,
which implies that with a set of $2k+1$ vertices, we can only find shortest
paths between them that cover at most
$\max(f_{2k+1}-1)\leq(2k+1)^{2}/2-1=2k^{2}+2k-1/2$ different vertical edges
which is less that the number $2(k^{2}+2)$ of all the vertical edges in
$P_{n}\,\square\,P_{3}$. This implies that if such a strong edge geodetic set
in $P_{n}\,\square\,P_{3}$ exists, it includes the vertex $(1,2)$. By
symmetry, it also includes the vertex $(n,2)$. But then, because $b\geq 2$,
the value of $f_{2k+1}(a,b,c)$ is less or equal to $((2k+1)^{2}-4)/2$ which is
again less than the number $2k^{2}+2k$ of different vertical edges in
$P_{n}\,\square\,P_{3}$.

Since in both cases we got a contradiction, we conclude that
$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{3})>\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{2})$. ∎

Propositions 4.2 and 4.3, together with Lemma 2.1 for $m=3$, and Lemma 4.1
imply Theorem 1.2.

##  5 Proof of Theorem 1.3

######  Lemma 5.1.

$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{4})\leq\left\lceil
2\sqrt{n}~{}\right\rceil+1$.

###### Proof.

Use Algorithm 1 and cover horizontal edges in the first row and in the last
row in the same way as in the proof of Theorem 1.1. To the existing vertex set
from Algorithm 1, add vertex $(n,2)$ and connect it with $(1,1)$ by a geodesic
that covers all horizontal edges from the second row (Fig. 7a) and with
$(1,4)$ by a geodesic that covers all horizontal edges from the third row
(Fig. 7b).

|
---|---
a | b
Figure 7: $(1,1)$,$(n,2)$-geodesic and $(1,4)$,$(n,2)$-geodesic.

∎

By Lemma 5.1 and Lemma 2.1 for $m=4$, we know that for every $n\geq 2$, the
strong edge geodetic number $\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{4})$
is either $\left\lceil 2\sqrt{n}~{}\right\rceil$ or $\left\lceil
2\sqrt{n}~{}\right\rceil+1$. From Lemma 2.2 we see that Theorem 1.3 says that
$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{4})=\left\lceil
2\sqrt{n}~{}\right\rceil$ except when $n=k^{2}$, $n=k^{2}+k$, or $n=k^{2}+2k$
for some $k\in\mathbb{N}$. Hence it is enough to prove that when $n=k^{2}$,
$n=k^{2}+k$, or $n=k^{2}+2k$ there is no strong edge geodetic set of size
$\left\lceil 2\sqrt{n}~{}\right\rceil$ and to find a strong edge geodetic set
of size $\left\lceil 2\sqrt{n}~{}\right\rceil$ in the other cases.

First, let us show that there exists a strong edge geodetic set of size
$\left\lceil 2\sqrt{n}~{}\right\rceil$ for $P_{n}\,\square\,P_{4}$ when
$n=k^{2}+h$ for some $k\in\mathbb{N}$, where $1\leq h\leq k-1$, or $k+1\leq
h\leq 2k-1$.

######  Proposition 5.2.

If $n=k^{2}+h$, $n\geq 3$, $k\geq 1$, where $1\leq h\leq k-1$ or $k+1\leq
h\leq 2k-1$, then

$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{4})\leq\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{2}).$

###### Proof.

To cover all the vertical edges and the horizontal edges in the second row, we
will adjust Algorithm 1. We divide this adjustment into two cases.

######  Case 1:

$n=k^{2}+h$, $1\leq h\leq k-1$ (see Fig. 8).
First, let us use Algorithm 1. In the next step replace the existing vertex
$b_{k+1}=(k^{2},1)$ with the vertex $c=(n,3)$ and for $j=h,\dots,1$ replace
the existing $a_{j}$,$b_{k+1}$-geodesic with two shortest paths, the
$a_{j+1}$,$c$-geodesic (it exists because $h\leq k-1$) that covers the edges
$(k^{2}+j,1)(k^{2}+j,2)$ and $(k^{2}+j,2)(k^{2}+j,3)$, and the
$b_{j+1}$,$c$-geodesic that covers the edge $(k^{2}+j,3)(k^{2}+j,4)$. This
replacement is well defined because we replaced all the shortest paths that
had one endpoint at $b_{k+1}$ and added some new shortest paths that have one
endpoint at $c$, so the condition that for each pair of vertices from the set
$\\{a_{1},\dots,a_{k},b_{1},\dots,b_{k},c\\}$ we only use at most one shortest
path, still holds.

|  |  |  |
---|---|---|---|---
| $\to$ |  |  |
| $\to$ |  | $+$ |
| $\to$ |  | $+$ |
|  |  |  |
|  |  |  |
Figure 8: Strong edge geodetic set in $P_{3^{2}+2}\,\square\,P_{4}$.

In this way we have adjusted Algorithm 1 such that it covers all vertical
edges in $P_{n}\,\square\,P_{4}$, while it uses neither the
$a_{1}$,$c$-geodesics nor the $b_{1}$,$c$-geodesics. This means that we can
add the $a_{1}$,$c$-geodesic that covers all the horizontal edges in the
second row and the $b_{1}$,$c$-geodesic that covers all the horizontal edges
in the third row. Some edges from the first row are already covered with the
$a_{h+1}$,$c$-geodesic, but the rest of them can be covered with the unique
$a_{1}$,$a_{k}$-geodesic. By symmetry, some of the horizontal edges from the
fourth row are covered with the $b_{h+1}$,$c$-geodesic, and the other ones are
covered by the $b_{1}$,$b_{k}$-geodesic.

######  Case 2:

$n=k^{2}+h$, $k+1\leq h\leq 2k-1$ (see Fig. 9).
In this case, because $h\leq 2k-1$, Algorithm 1 never uses a
$a_{k+1}$,$b_{k}$-geodesic. It also never uses the unique
$a_{k+1}$,$b_{k+1}$-geodesic. If we add this shortest path, we can replace the
existing $b_{h-k}$,$a_{k+1}$-geodesic (this shortest path covers the vertical
edges in the $n$-th column) with the one that covers the vertical edges in the
$(k(k+1)+1)$-th column (in Algorithm 1 covered by the
$a_{k+1}$,$b_{1}$-geodesic). Observe that this step does nothing if $h=1$.
This way we can replace the existing $a_{k+1}$,$b_{1}$-geodesic with the one
that covers all the horizontal edges in the third row.

Also, if we add the $a_{k+1}$,$b_{k}$-geodesic that covers all the vertical
edges in the $(k^{2}+1)$-th column, we can replace the existing
$a_{1}$,$b_{k+1}$-geodesic with the one that covers all the horizontal edges
in the second row.

| $\to$ |
---|---|---

| $\to$ |
---|---|---

| $\to$ |
---|---|---

Figure 9: Strong edge geodetic set in $P_{3^{2}+2\cdot 3-1}\,\square\,P_{4}$.

In the same way as in $P_{n}\,\square\,P_{2}$ we now cover the horizontal
edges in the first row (using the $a_{1}$,$a_{k+1}$-geodesic) and in the
fourth row (using the $b_{1}$,$b_{k+1}$-geodesic) of $P_{n}\,\square\,P_{4}$.

Since in all three cases we found a strong edge geodetic set of size
$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{2})$, we can conclude that
$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{4})\leq\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{2})$ for all $n\in\mathbb{N}$ when $n\not=k^{2}$,
$n\not=k^{2}-1$, and $n\not=k^{2}+k$ for some $k\in\mathbb{N}$. ∎

We will now show that there is no strong edge geodetic set of size
$\left\lceil 2\sqrt{n}\right\rceil$ for $P_{n}\,\square\,P_{4}$ when
$n=k^{2}-1$, $k^{2}$, or $k^{2}+k$ for some $k\in\mathbb{N}$.

######  Proposition 5.3.

If $n=k^{2}$, $n=k^{2}-1$, or $n=k^{2}+k$ for some $k\geq 2$,
$k\in\mathbb{N}$, then

$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{4})>\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{2}).$

###### Proof.

Let us define the function

$f_{s}(a,b,c,d)=ab+bc+cd+2ac+2bd+3ad$

which gives an upper bound on how many different vertical edges can be covered
with shortest paths between $s$ vertices, where $a$ vertices are in the first
row, $b$ vertices in the second row, $c$ vertices in the third row, and $d$
vertices in the fourth row of $P_{n}\,\square\,P_{4}$. The maximum values of
function $f_{s}$ under some bounds are again computed by computer and are
gathered in Table 1.

conditions |  |  | upper bound
---|---|---|---
$a,b,c,d\geq 0$ |  |  | $f_{s}(a,b,c,d)\leq{1\over 4}(3s^{2})$
$a,c,d\geq 0$, | $b\geq 1$ |  | $f_{s}(a,b,c,d)\leq{1\over 12}(9s^{2}-8)$
$a,b,c,d\geq 0$, | $b+c\geq 2$ |  | $f_{s}(a,b,c,d)\leq{1\over 4}(3s^{2}-8)$
$a,b,c,d\geq 0$, | $b+c\geq 3$ |  | $f_{s}(a,b,c,d)\leq{1\over 4}(3s^{2}-18)$
Table 1: Maximal values of function $f_{s}(a,b,c,d)$.

Every strong edge geodetic set $S$ has to include at least one vertex from the
first column, otherwise it would not be possible to cover the edge
$(1,1)(1,2)$. Similarly, every strong edge geodetic set includes at least one
vertex from the last column. Depending on a strong edge geodetic set $S$ in
$P_{n}\,\square\,P_{4}$ we will define a type of first or last column of
vertices. All the types for a strong edge geodetic set with at least one
vertex in the first and at least one vertex in the last column are gathered in
Table 2. For example, if $(1,1),(1,2)\in S$ and $(1,3),(1,4)\not\in S$, we say
that the first column of vertices in $P_{n}\,\square\,P_{4}$ is of type $D$.
Symmetrically, if $(1,1),(1,2)\not\in S$ and $(1,3),(1,4)\in S$, we also say
that the first column of vertices in $P_{n}\,\square\,P_{4}$ is of type $D$.
We symmetrically define the type of the last column.

Type $T$ | type in first column |  | $r(T)$
---|---|---|---
$A$ |  |  | $7$
$B$ |  |  | $2$
$C$ |  |  | $4$
$D$ |  |  | $1$
$E$ |  |  | $1$
$F$ |  |  | $2$
$G$ |  |  | $0$
$H$ |  |  | $3$
$I$ |  |  | $1$
Table 2: Different types of a strong edge geodetic set in the first or the
last column.

For a shortest path $P$ in $P_{n}\,\square\,P_{4}$, let $E_{i}(P)$ denote the
set of edges in $i$-th column, that is,

$E_{i}(P)=E(P)\cap\\{(i,1)(i,2),(i,2)(i,3),(i,3)(i,4)\\}.$

For a strong edge geodetic covering $C=\\{P_{x,y}\\}$ set

$r_{C}^{1}=\sum_{\\{x,y\\}\in\binom{S}{2}}|E_{1}(P_{x,y})|-3.$

Roughly speaking, $r_{C}^{1}$ measures redundancy of the strong edge geodetic
covering in the first column of $P_{n}\,\square\,P_{4}$. Analogously, the
redundancy $r_{C}^{n}$ with respect to the last column is introduced.

For each type $T$ of the first column determined by $S$, we can now compute
the minimum number of redundant coverings in the first column of edges as
$r_{1}(T)=\min_{C}\\{r_{C}^{1}\\}$, where $C$ is a strong edge geodetic
covering for a strong edge geodetic set $S$, where the first column in
$P_{n}\,\square\,P_{4}$ is of type $T$. Similarly we can define the minimum
number of redundant coverings in the last column of edges, $r_{n}(T)$. By
symmetry, these two numbers are the same, so we can denote
$r(T)=r_{1}(T)=r_{n}(T)$. For each type $T$, the number $r(T)$ is listed in
the last column of Table 2.

We will show how to compute $r(C)$ for type $C$, for other types it is
similar. We can without loss of generality assume
$\\{(1,1),(1,2),(1,4)\\}\subset S$. Between the pairs of these three vertices,
there are three unique shortest paths $P_{1}$, $P_{2}$, and $P_{3}$. To cover
the horizontal edge $(1,3)(2,3)$ we need another shortest path $P_{4}$ that
has one endvertex in the vertex set $\\{(1,1),(1,2),(1,4)\\}$. Because
$(1,3)\not\in S$, this path includes at least one vertical edge from the first
column, which implies

$\sum_{\\{x,y\\}\in\binom{S}{2}}|E_{1}(P_{x,y})|-3\geq|E_{1}(P_{1})|+|E_{1}(P_{2})|+|E_{1}(P_{3})|+|E_{1}(P_{4})|-3\geq
3.$

Suppose now that $S$ is a strong edge geodetic set for $P_{n}\,\square\,P_{4}$
of cardinality $|S|=\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{2})$. We
distinguish four different cases.

######  Case 1:

$S$ does not contain any vertex from the set $\\{(1,2),(1,3),(n,2),(n,3)\\}$.
In this case the first and the last column are either of type $F$ or type $G$,
which implies that $r_{1}+r_{n}\geq 4$. Because
$f_{s}(a,b,c,d)\leq{3s^{2}\over 4}$ when $a,b,c,d\geq 0$, it holds

$\displaystyle f_{s}(a,b,c,d)-4$ $\displaystyle\leq$
$\displaystyle{3\cdot(2k)^{2}\over 4}-4=3k^{2}-4<3n\text{ for }n=k^{2}-1;$
$\displaystyle f_{s}(a,b,c,d)-4$ $\displaystyle\leq$
$\displaystyle{3\cdot(2k)^{2}\over 4}-4=3k^{2}-4<3n\text{ for }n=k^{2};$
$\displaystyle f_{s}(a,b,c,d)-4$ $\displaystyle\leq$
$\displaystyle{3\cdot(2k+1)^{2}\over 4}-4=3k^{2}+3k-{13\over 4}<3n\text{ for
}n=k^{2}+k,$

for $s=\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{2})$.

######  Case 2:

$S$ contains at least three vertices from the second and the third row.
Because $f_{s}(a,b,c,d)\leq{1\over 4}(3s^{2}-18)$ when $a,b,c,d\geq 0$,
$b+c\geq 3$, it holds

$\displaystyle f_{s}(a,b,c,d)$ $\displaystyle\leq$ $\displaystyle{1\over
4}(3(2k)^{2}-18)=3k^{2}-{18\over 4}<3n\text{ for }n=k^{2}-1;$ $\displaystyle
f_{s}(a,b,c,d)$ $\displaystyle\leq$ $\displaystyle{1\over
4}(3(2k)^{2}-18)=3k^{2}-{18\over 4}<3n\text{ for }n=k^{2};$ $\displaystyle
f_{s}(a,b,c,d)$ $\displaystyle\leq$ $\displaystyle{1\over
4}(3(2k+1)^{2}-18)=3k^{2}+3k-{15\over 4}<3n\text{ for }n=k^{2}+k,$

for $s=\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{2})$.

######  Case 3:

$S$ contains exactly two vertices from the set $\\{(1,2),(1,3),(n,2),(n,3)\\}$
and no other vertex from the second and the third row.
If we look at all types of the first and the last column such that the
condition holds, we see that $r_{1}+r_{n}$ is always at least $2$ (observe
that type $G$ can only be combined with types $F$ and $H$). Because
$f_{s}(a,b,c,d)\leq{1\over 4}(3s^{2}-8)$ when $b+c\geq 2$, and $a,b,c,d\geq
0$, it holds

$\displaystyle f_{s}(a,b,c,d)-2$ $\displaystyle\leq$ $\displaystyle{1\over
4}(3(2k)^{2}-8)-2=3k^{2}-4<3n\text{ for }n=k^{2}-1;$ $\displaystyle
f_{s}(a,b,c,d)-2$ $\displaystyle\leq$ $\displaystyle{1\over
4}(3(2k)^{2}-8)-2=3k^{2}-4<3n\text{ for }n=k^{2};$ $\displaystyle
f_{s}(a,b,c,d)-2$ $\displaystyle\leq$ $\displaystyle{1\over
4}(3(2k+1)^{2}-8)-2=3k^{2}+3k-{13\over 4}<3n\text{ for }n=k^{2}+k,$

for $s=\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{2})$.

######  Case 4:

$S$ contains exactly one vertex from the set $\\{(1,2),(1,3),(n,2),(n,3)\\}$
and no other vertex from the second and the third row.
By symmetry, we can without loss of generality assume that
$(1,3),(n,2),(n,3)\not\in S$ and $(1,2)\in S$. This implies that the first
column is of type $C$, $D$, $E$, or $H$ and the last column is of type $F$ or
$G$. The sum of the number of redundant coverings for the first and the last
column is than at least $3$. Because $f_{s}(a,b,c,d)\leq{1\over 12}(9s^{2}-8)$
when $b+c\geq 2$ and $a,b,c,d\geq 0$, it holds

$\displaystyle f_{s}(a,b,c,d)-2$ $\displaystyle\leq$ $\displaystyle{1\over
12}(9(2k)^{2}-8)-3=3k^{2}-{11\over 3}<3n\text{ for }n=k^{2}-1;$ $\displaystyle
f_{s}(a,b,c,d)-2$ $\displaystyle\leq$ $\displaystyle{1\over
12}(9(2k)^{2}-8)-3=(3k^{2}-3)-{2\over 3}<3n\text{ for }n=k^{2};$
$\displaystyle f_{s}(a,b,c,d)-2$ $\displaystyle\leq$ $\displaystyle{1\over
12}(9(2k+1)^{2}-8)-3=(3k^{2}+3k)-{37\over 12}<3n\text{ for }n=k^{2}+k,$

for $s=\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{2})$.

Since $3n$ is the number of all vertical edges in $P_{n}\,\square\,P_{4}$, it
holds $|S|>\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{2})$ in every case
above. This is a contradiction with the assumption that $S$ is a strong edge
geodetic set of $P_{n}\,\square\,P_{4}$ of cardinality $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{2})$.

Because all four cases led us to a contradiction, we can conclude that for
$P_{n}\,\square\,P_{4}$, where $n=k^{2}-1,k^{2}$, or $k^{2}+k$ for some
$k\in\mathbb{N}$, there is no strong edge geodetic set of size
$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{2})$. By Lemma 5.1 this means
that $\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{4})=\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{2})+1$ when $n=k^{2}-1,k^{2}$, or $k^{2}+k$ for
some $k\in\mathbb{N}$. In other words, $\operatorname{\rm
sg_{e}}(P_{k^{2}-1}\,\square\,P_{4})=\operatorname{\rm
sg_{e}}(P_{k^{2}}\,\square\,P_{4})=2k+1$ and $\operatorname{\rm
sg_{e}}(P_{k^{2}+k}\,\square\,P_{4})=2k+2$. Also, because
$k^{2}-1=(k-1)^{2}+2(k-1)$, we have $\operatorname{\rm
sg_{e}}(P_{k^{2}+2k}\,\square\,P_{4})=2k+3$. ∎

##  6 Upper bounds

In this concluding section we give two upper bounds on $\operatorname{\rm
sg_{e}}(P_{n}\,\square\,P_{m})$.

######  Proposition 6.1.

If $n\geq 2$ and $m\geq 2$, then

$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{m})\leq\left\lceil
2\sqrt{n}~{}\right\rceil+\left\lceil 2\sqrt{m-2}~{}\right\rceil.$

###### Proof.

First we cover all the vertical edges in $P_{n}\,\square\,P_{m}$ by using
Algorithm 1. This algorithm uses $\left\lceil 2\sqrt{n}~{}\right\rceil$
vertices from the first and the last row. We also, similarly as in
$P_{n}\,\square\,P_{2}$, use these vertices to cover the horizontal edges from
the first and the last row (Fig. 10a).

|  |
---|---|---
a |  | b
|  |
c |  | d
Figure 10: Strong edge geodetic set for $P_{n}\,\square\,P_{m}$ with
cardinality $\left\lceil 2\sqrt{n}~{}\right\rceil+\left\lceil
2\sqrt{m-2}~{}\right\rceil$ for $n=14$ and $m=8$.

In second step we look at the subgraph $H$ of $P_{n}\,\square\,P_{m}$ without
the first and the last row (Fig. 10b). $H$ is isomorphic to
$P_{n}\,\square\,P_{m-2}$. To cover all the horizontal edges from $H$, we use
Algorithm 1 on $H$ rotated by $90$ degrees, which is the same as using
Algorithm 1 on $P_{m-2}\,\square\,P_{n}$ (Fig. 10c). This algorithm uses
exactly $\left\lceil 2\sqrt{m-2}~{}\right\rceil$ vertices and cover all the
horizontal edges from $H$, which are exactly the edges that have not been
covered in the first part of the proof. ∎

With a similar, but a bit more involved, idea as in the proof of Proposition
6.1, we are going to prove the following proposition.

######  Proposition 6.2.

If $n\geq 3$ and $m\geq 3$, then

$\operatorname{\rm sg_{e}}(P_{n}\,\square\,P_{m})\leq\left\lceil
2\sqrt{n+2}\right\rceil+\left\lceil 2\sqrt{m\phantom{!}}\right\rceil-4.$

###### Proof.

First we will adjust Algorithm 1 such that it will use all the corner
vertices, that is $(1,1),(1,m),(n,1),(n,m)$. We call the new algorithm
Algorithm 1*. For $n=k^{2}+h$, where $h=0$ or $k+1\leq h\leq 2k$, Algorithm 1
already uses all the corner vertices. When $n=k^{2}+h$, $1\leq h\leq k$,
redefine the vertex $a_{k}$ as $a_{k}=(n,1)$. The shortest paths between
vertices $a_{k}$ and $b_{i}$ in Algorithm 1* are the ones that cover the same
vertical edges as shortest paths between vertices $a_{k}$ and $b_{i}$ in
Algortihm 1. An example output of this algorithm is shown in Fig. 11.

Figure 11: Strong edge geodetic set of $P_{4^{2}+2}\,\square\,P_{5}$ from
Algorithm 1*.

When $n=k^{2}$, $n=k^{2}+k-1$, $n=k^{2}+k$, or $n=k^{2}+2k$ for some
$k\in\mathbb{N}$, we will cover the vertical edges in $P_{n}\,\square\,P_{m}$
in the following way. First, we use Algorithm 1* with
$\left\lceil\sqrt{n}~{}\right\rceil$ vertices $V_{1}$. To $V_{1}$ we add
$c=((k-1)^{2}+k,m)$. We can then cover the vertical edges covered by the
$(1,1),(n,m)$-geodesic and the $(n,1),(1,m)$-geodesic with $(1,1),c$-geodesic
and $(n,1),c$-geodesic. In this way, we can remove shortest paths between
corner vertices (Fig. 12).

| $\to$ |
---|---|---
| $\to$ |
Figure 12: Covering vertical edges in $P_{n}\,\square\,P_{m}$ without using
shortest paths between vertices $(1,1)$ and $(n,m)$ and between vertices
$(n,1)$ and $(1,m)$.

When $n=k^{2}+h$; $k,h\in\mathbb{N}$; $1\leq h\leq k-2$, we will adjust
Algorithm 1* to cover all the vertical edges with the same vertex set and
without using the shortest paths between vertices $a_{1}$ and $b_{k+1}$ and
between vertices $a_{k}$ and $b_{1}$. First we notice that Algorithm 1* does
not use the unique $a_{k}$,$b_{k+1}$-geodesic. If we add it, we can replace
the $a_{h}$,$b_{k+1}$-geodesic with the one that covers all the vertical edges
in the $(k^{2}+1)$-th column. We can then remove the
$a_{1}$,$b_{k+1}$-geodesic (it also covers the vertical edges in the
$(k^{2}+1)$-th column). Algorithm 1* also does not use the
$a_{k-1}$,$b_{k+1}$-geodesic. If we add the $a_{k-1}$,$b_{k+1}$-geodesic that
covers all the vertical edges in the $((k-1)^{2}+k)$-th column, we can remove
the $a_{k}$,$b_{k+1}$-geodesic.

When $n=k^{2}+h$, $k,h\in\mathbb{N}$, $k+1\leq h\leq 2k-1$, we can use a
similar adjustment as in the proof of Theorem 1.3 for $n=k^{2}+h$, $k+1\leq
h\leq 2k-1$, and remove the shortest paths between vertices $a_{1}$ and
$b_{k+1}$ and between vertices $a_{k+1}$ and $b_{1}$ that cover the horizontal
edges in the second and the third row.

In the first part of the proof we defined the algorithm that uses $\left\lceil
2\sqrt{n+2}~{}\right\rceil$ vertices and covers all the vertical rows in
$P_{n}\,\square\,P_{m}$, while it uses neither the $(1,1)$,$(n,m)$-geodesic,
nor the $(1,m)$,$(n,1)$-geodesic.

To cover the horizontal edges, we use Algorithm 1* on rotated
$P_{n}\,\square\,P_{m}$ by $90$ degrees. This part will use
$\left\lceil\sqrt{m}~{}\right\rceil$ vertices, where four
($(1,1),(1,m),(n,1),(n,m)$) of them are already used in the first part.
Because the first part does not use shortest paths between these four
vertices, the condition that between any two vertices we use at most one
shortest path still holds.

In the first and in the second part we have covered all the edges in
$P_{n}\,\square\,P_{m}$, using exactly
$\left\lceil\sqrt{n+2}~{}\right\rceil+\left\lceil\sqrt{m}~{}\right\rceil-4$
vertices. ∎

If we combine all the results from this paper, we can see that the bound from
Proposition 6.1 is sharp when $m=2$ and is not sharp for $m=3$ and $m=4$. The
bounds from Proposition 6.2 are sharp when $m=3$ and $n=k^{2}$ or $k^{2}+k$
for some integer $k$, as well as when $m=4$ and $n=k^{2}$, $k^{2}+k$ or
$k^{2}+2k$ for some integer $k$.

## References

  * [1] V. Gledel and V. Iršič.  Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes.  Bull. Malays. Math. Sci. Soc., 43:2757–2767, 2020.
  * [2] V. Gledel, V. Iršič, and S. Klavžar.  Strong geodetic cores and Cartesian product graphs.  Appl. Math. Comput., 363:124609, 2019.
  * [3] F. Harary, E. Loukakis, and C. Tsouros.  The geodetic number of a graph.  Math. Comput. Model., 17:89–95, 1993.
  * [4] V. Iršič.  Strong geodetic number of Complete bipartite graphs and of graphs with specified diameter.  Graphs Combin., 43:443–456, 2018.
  * [5] V. Iršič and S. Klavžar.  Strong geodetic problem on Cartesian products of graphs.  RAIRO Oper. Res., 52:205–216, 2018.
  * [6] V. Iršič and M. Konvalinka.  Strong geodetic problem on complete multipartite graphs.  Ars Math. Contemp., 17:481–491, 2019.
  * [7] S. Klavžar and P. Manuel.  Strong geodetic problem in grid-like architectures.  Bull. Malays. Math. Sci. Soc., 41:1671–1680, 2018.
  * [8] P. Manuel, S. Klavžar, A. Xavier, A. Arokiaraj, and E. Thomas.  Strong edge geodetic problem in networks.  Open Math., 15:1225–1235, 2017.
  * [9] P. Manuel, S. Klavžar, A. Xavier, A. Arokiaraj, and E. Thomas.  Strong geodetic problem in networks.  Discuss. Math. Graph Theory, 40:307–321, 2020.
  * [10] M. Mezzini.  An $O(mn^{2})$ algorithm for computing the strong geodetic number in outerplanar graphs.  Discuss. Math. Graph Theory, 2020.  doi:10.7151/dmgt.2311.
  * [11] A. P. Santhakumaran and J. John.  Edge geodetic number of a graph.  J. Discrete Math. Sci. Cryptogr., 10:415–432, 2007.
  * [12] Z. Wang, Y. Mao, H. Ge, and C. Magnant.  Strong geodetic number of graphs and connectivity.  Bull. Malays. Math. Sci. Soc., 43:2443–2453, 2020.