22 2102

# New Optimal Results on Codes for Location in Graphs††thanks: An extended
abstract [1] of the paper has been presented at the Fifth Russian Finnish
Symposium on Discrete Mathematics.††thanks: Research supported by the Academy
of Finland grant 338797.

Ville Junnila
Department of Mathematics and Statistics
University of Turku
Turku FI-20014  Finland
<EMAIL_ADDRESS>
Tero Laihonen
Department of Mathematics and Statistics
University of Turku
Turku FI-20014  Finland
<EMAIL_ADDRESS>
Tuomo Lehtilä
Department of Mathematics and Statistics
University of Turku
Turku FI-20014 Research supported by the University of Turku Graduate School
(UTUGS), the Vilho, Yrjö and Kalle Väisälä Foundation, and the Jenny and Antti
Wihuri Foundation. Finland
<EMAIL_ADDRESS>
###### Abstract

In this paper, we broaden the understanding of the recently introduced
concepts of solid-locating-dominating and self-locating-dominating codes in
various graphs. In particular, we present the optimal, i.e., smallest
possible, codes in the infinite triangular and king grids. Furthermore, we
give optimal locating-dominating, self-locating-dominating and solid-locating-
dominating codes in the direct product $K_{n}\times K_{m}$ of complete graphs.
We also present optimal solid-locating-dominating codes for the Hamming graphs
$K_{q}\square K_{q}\square K_{q}$ with $q\geq 2$.

###### keywords:

Location-domination, solid-location-domination, self-location-domination, king
grid, direct product, Hamming graph

††volume: 185††issue: 1

New Optimal Results on Codes for Location in Graphs

##  1 Introduction

Sensor networks consist of sensors monitoring various places and connections
between these places (see [2]). A sensor network is modeled as a simple and
undirected graph $G=(V(G),E(G))=(V,E)$. In this context, a sensor can be
placed on a vertex $v$ and its closed neighbourhood $N[v]$ represents the set
of locations that the sensor monitors. Besides assuming that graphs are simple
and undirected, we also assume that they are connected and have cardinality at
least two. In the following, we present some terminology and notation. The
closed neighbourhood of $v$ is defined $N[v]=N(v)\cup\\{v\\}$, where $N(v)$ is
the open neighbourhood of $v$, that is, the set of vertices adjacent to $v$. A
code $C$ is a nonempty subset of $V$ and its elements are codewords. The
codeword $c\in C$ _covers_ a vertex $v\in V$ if $v\in N[c]$. We denote the set
of codewords covering $v$ in $G$ by

$I(G,C;v)=I(G;v)=I(C;v)=I(v)=N[v]\cap C\text{.}$

The set $I(v)$ is called an identifying set or an $I$_-set_. We say that a
code $C\subseteq V$ is dominating in $G$ if $I(C;u)\neq\emptyset$ for all
$u\in V$. If the sensors are placed at the locations corresponding to the
codewords, then each vertex is monitored by the sensors located in $I(v)$.
More explanation regarding location detection in the sensor networks can be
found in [3, 4, 5].

Let us now define identifying codes, which were first introduced by Karpovsky
et al. in [6]. For numerous papers regarding identifying codes and related
topics, the interested reader is referred to the online bibliography [2].

###### Definition 1.1

A code $C\subseteq V$ is _identifying_ in $G$ if for all distinct $u,v\in V$
we have $I(C;u)\neq\emptyset$ and

$I(C;u)\neq I(C;v)\text{.}$

An identifying code $C$ in a finite graph $G$ with the smallest cardinality is
called _optimal_ and the number of codewords in an optimal identifying code is
denoted by $\gamma^{ID}(G)$.

Identifying codes require unique $I$-sets for codewords as well as for non-
codewords. However, if we omit the requirement of unique $I$-sets for
codewords, then we obtain the following definition of _locating-dominating
codes_ , which were first introduced by Slater in [7, 8, 9].

###### Definition 1.2

A code $C\subseteq V$ is _locating-dominating_ in $G$ if for all distinct
$u,v\in V\setminus C$ we have $I(C;u)\neq\emptyset$ and

$I(C;u)\neq I(C;v)\text{.}$

Notice that an identifying code in $G$ is also locating-dominating (by the
definitions). In [10], self-locating-dominating and solid-locating-dominating
codes have been introduced and, in [11, 12], they have been further studied.
The definitions of these codes are given as follows.

###### Definition 1.3

Let $C\subseteq V$ be a code in $G$.

  * (i)

We say that $C\subseteq V$ is _self-locating-dominating code_ in $G$ if for
all $u\in V\setminus C$ we have $I(C;u)\neq\emptyset$ and

$\bigcap_{c\in I(C;u)}N[c]=\\{u\\}\text{.}$

  * (ii)

We say that $C\subseteq V$ is _solid-locating-dominating code_ in $G$ if for
all distinct $u,v\in V\setminus C$ we have

$I(C;u)\setminus I(C;v)\neq\emptyset\text{.}$

Observe that since $G$ is a connected graph on at least two vertices, a self-
locating-dominating and solid-locating-dominating code is always dominating.
Analogously to identifying codes, in a finite graph $G$, we say that
dominating, locating-dominating, self-locating-dominating and solid-locating-
dominating codes with the smallest cardinalities are _optimal_ and we denote
the cardinality of an optimal code by $\gamma(G)$,
$\gamma^{LD}(G),\gamma^{SLD}(G)$ and $\gamma^{DLD}(G)$, respectively.

In the following theorem, we offer characterizations of self-locating-
dominating and solid-locating-dominating codes for easier comparison of them.

######  Theorem 1.4 ([10])

Let $G=(V,E)$ be a connected graph on at least two vertices:

  * (i)

A code $C\subseteq V$ is self-locating-dominating if and only if for all
distinct $u\in V\setminus C$ and $v\in V$ we have

$I(C;u)\setminus I(C;v)\neq\emptyset\text{.}$

  * (ii)

A code $C\subseteq V$ is solid-locating-dominating if and only if for all
$u\in V\setminus C$ we have $I(C;u)\neq\emptyset$ and

$\left(\bigcap_{c\in I(C;u)}N[c]\right)\setminus C=\\{u\\}\text{.}$

Based on the previous theorem, we obtain the following corollary.

###### Corollary 1.5

If $C$ is a self-locating-dominating or solid-locating-dominating code in $G$,
then $C$ is also solid-locating-dominating or locating-dominating in $G$,
respectively. Furthermore, for a finite graph $G$, we have

$\gamma^{LD}(G)\leq\gamma^{DLD}(G)\leq\gamma^{SLD}(G)\text{.}$

The structure of the paper is described as follows. First, in Section 2, we
obtain optimal self-locating-dominating and solid-locating-dominating codes in
the infinite triangular and king grids, i.e., the smallest possible codes
regarding their density (a concept defined later). Regarding the triangular
grid, the proofs are rather simple and straightforward, but they serve as nice
introductory examples to the concepts of solid-location-domination and self-
location-domination. However, the case with the king grid is more interesting;
in particular, the proof of the lower bound for solid-location-domination is
based on global arguments instead of only local ones, which are more usual in
domination type problems. Then, in Section 3, we give optimal locating-
dominating, self-locating-dominating and solid-locating-dominating codes in
the direct product $K_{n}\times K_{m}$ of complete graphs, where $2\leq n\leq
m$. Finally, in Section 4, we present optimal solid-locating-dominating codes
for graphs $K_{q}\square K_{q}\square K_{q}$ with $q\geq 2$.

##  2 Triangular and king grids

In this section, we consider solid-location-domination and self-location-
domination in the so called infinite triangular and king grids, which are
widely studied graphs in the field of domination (see [2]). As defined in the
introduction, for finite graphs, the optimality of a code has been defined
using the minimum cardinality. However, this method is not valid for the
infinite graphs of this section. Hence, we need to use the usual concept of
density of a code (see various papers concerning infinite grids in [2]). Let
us first consider the infinite triangular grid.

###### Definition 2.1

Let $G=(V,E)$ be a graph with the vertex set

$V=\left\\{i(1,0)+j\left(\frac{1}{2},\frac{\sqrt{3}}{2}\right)\mid
i,j\in\mathbb{Z}\right\\}$

and two vertices are defined to be adjacent if their Euclidean distance is
equal to one. The obtained graph $G$ is called the infinite triangular grid
and it is illustrated in Figure 1. We further denote
$v(i,j)=i(1,0)+j\left(\frac{1}{2},\frac{\sqrt{3}}{2}\right)$. Let $R_{n}$ be
the subgraph of $G$ induced by the vertex set $V_{n}=\\{v(i,j)\mid|i|,|j|\leq
n\\}$. The _density_ of a code in $G$ is now defined as follows:

$D(C)=\limsup_{n\rightarrow\infty}\frac{|C\cap V_{n}|}{|V_{n}|}$

We say that a code is _optimal_ if there exists no other code with smaller
density.

$u$$v$$w$ Figure 1: Triangular grid with the vertices $v=v(0,0)$, $u=v(1,-1)$
and $w=v(1,1)$.

In the following theorem, optimal self-locating-dominating and solid-locating-
dominating codes are given in the triangular grid. The methods used in the
proof are rather typical for domination type of problems. However, we present
the proof for completeness and as an introductory example.

###### Theorem 2.2

Let $G=(V,E)$ be the triangular grid. The code

$C=\\{v(i,j)\mid i,j\equiv 0\pmod{2}\\}$

is self-locating-dominating in $G$ and, therefore, also solid-locating-
dominating. The density of the code $C$ is equal to $1/4$ and there exists no
self-locating-dominating or solid-locating-dominating code with smaller
density, i.e., the code is optimal in both cases.

###### Proof 2.3

Let us first show that the code $C$ is self-locating-dominating in the
triangular grid $G$. The proof now divides into the following cases depending
on the parity of $i$ and $j$ in $v(i,j)$:

  * •

If $i$ is odd and $j$ is even, then $I(v(i,j))=\\{v(i-1,j),v(i+1,j)\\}$ and
$N[v(i-1,j)]\cap N[v(i+1,j)]=\\{v(i,j)\\}$.

  * •

Analogously, if $i$ is even and $j$ is odd, then
$I(v(i,j))=\\{v(i,j-1),v(i,j+1)\\}$ and $N[v(i,j-1)]\cap
N[v(i,j+1)]=\\{v(i,j)\\}$.

  * •

Finally, if $i$ and $j$ are both odd, then
$I(v(i,j))=\\{v(i-1,j+1),v(i+1,j-1)\\}$ and $N[v(i-1,j+1)]\cap
N[v(i+1,j-1)]=\\{v(i,j)\\}$.

Thus, as $v(i,j)$ is a codeword for even $i$ and $j$, the code $C$ is self-
locating-dominating in $G$. Furthermore, we have $D(C)=\frac{1}{4}$ since
$v(i,j)$ is a codeword if and only if $i$ and $j$ are both even. Notice that
$C$ is also a solid-locating-dominating code.

For the lower bound, assume that $C^{\prime}$ is a solid-locating-dominating
code in $G$. Immediately, by the definition of solid-locating-dominating
codes, we know that $|I(C^{\prime};u)|\geq 2$ for any non-codeword $u$.
Therefore, by counting in two ways the pairs $(u,c)$, where $c\in
C^{\prime}\cap V_{n}$ and $u\in N[c]\cap V_{n-1}$, we obtain that
$7|C^{\prime}\cap V_{n}|\geq|C^{\prime}\cap
V_{n-1}|+2(|V_{n-1}|-|C^{\prime}\cap V_{n-1}|)\geq 2|V_{n-1}|-|C^{\prime}\cap
V_{n-1}|\geq 2|V_{n-1}|-|C^{\prime}\cap V_{n}|$, which is equivalent to
$|C^{\prime}\cap V_{n}|\geq|V_{n-1}|/4$. Thus, we may estimate the density of
$C^{\prime}$ as follows:

$D(C^{\prime})=\limsup_{n\rightarrow\infty}\frac{|C^{\prime}\cap
V_{n}|}{|V_{n}|}\geq\limsup_{n\rightarrow\infty}\frac{|V_{n-1}|/4}{|V_{n}|}=\frac{1}{4}\text{.}$

Next we consider the more interesting problems of solid-location-domination
and self-location-domination in the infinite king grid. Let us first begin by
defining the grid and the density of a code in it.

###### Definition 2.4

Let $G=(V,E)$ be a graph with $V=\mathbb{Z}^{2}$ and for the vertices
$v=(v_{1},v_{2})\in V$ and $u=(u_{1},u_{2})\in V$ we have $vu\in E$ if and
only if $|v_{1}-u_{1}|\leq 1$ and $|v_{2}-u_{2}|\leq 1$. The obtained graph
$G$ is called the infinite king grid. Further let $V_{n}$ be a subset of $V$
such that $V_{n}=\\{(x,y)\mid|x|\leq n,|y|\leq n\\}$. The _density_ of a code
$C\subseteq V=\mathbb{Z}^{2}$ is now defined as

$D(C)=\underset{n\to\infty}{\lim\sup}\frac{|C\cap V_{n}|}{|V_{n}|}.$

We say that a code is _optimal_ if there exists no other code with smaller
density.

In what follows, we first consider solid-location-domination in the king grid.
In the following theorem, we present a solid-locating-dominating code in the
king grid with density $1/3$. Later, in Theorem 2.9, it is shown that the code
is optimal.

###### Theorem 2.5

Let $G=(V,E)$ be the king grid. The code

$C=\left\\{(x,y)\in\mathbb{Z}^{2}\mid|x|+|y|\equiv 0\pmod{3}\right\\}$

is solid-locating-dominating in $G$ and its density is $1/3$.

###### Proof 2.6

Let $C=\left\\{(x,y)\in\mathbb{Z}^{2}\mid|x|+|y|\equiv 0\mod 3\right\\}$ be a
code in $G$ (illustrated in Figure 2). By the definition, it is immediate that
the density of $C$ is equal to $1/3$. In order to show that $C$ is a solid-
locating-dominating code in $G$, we prove that the condition of Theorem
1.4(ii) holds for every non-codeword of $G$. Let $u=(x,y)\in\mathbb{Z}^{2}$ be
a vertex not belonging to $C$. Suppose first that $x=0$ and $y>0$. Now, if
$y\equiv 1\pmod{3}$, then $I(u)=\\{u+(0,-1),u+(-1,1),u+(1,1)\\}$ and
$N[u+(0,-1)]\cap N[u+(-1,1)]\cap N[u+(1,1)]=\\{u\\}$, else $y\equiv 2\pmod{3}$
implying $I(u)=\\{u+(-1,0),u+(1,0),u+(0,1)\\}$ and $(N[u+(-1,0)]\cap
N[u+(1,0)]\cap N[u+(0,1)])\setminus C=\\{u\\}$. Thus, the required condition
is met. The case with $y<0$ is analogous. Moreover, the case with $y=0$ is
symmetrical to the one with $x=0$. Hence, we may assume that $x\neq 0$ and
$y\neq 0$.

Suppose then that $x\geq 1$ and $y\geq 1$. Now we have either
$I(u)=\\{u+(0,-1),u+(-1,0),u+(1,1)\\}$ or
$I(u)=\\{u+(0,1),u+(1,0),u+(-1,-1)\\}$. In both cases, we obtain that
$\bigcap_{c\in I(u)}N[c]=\\{u\\}$ and the condition is satisfied. The other
(three) cases with $x\leq-1$ or $y\leq-1$ can be handled analogously. Thus, in
conclusion, $C$ is a solid-locating-dominating code in $G$.

Figure 2: The darkened squares form a solid-locating-dominating code of
density $\frac{1}{3}$ in the king grid.

Usually, the best known constructions for domination type codes in infinite
grids are formed by a repetition of a finite pattern. However, this is not the
case with the code $C$ of the previous theorem. Another observation is that
the codeword $c=(0,0)$ has a special role as a sort of center of the code. In
particular, the density of the code (or more precisely the ratio $|C\cap
V_{n}|/|V_{n}|$) in the close proximity of $c$ is less than $1/3$. Consider
now the lower bound on the density of a solid-locating-dominating code.
Usually, the lower bounds are obtained by locally studying the symmetric
difference of closed neighbourhoods of vertices or the domination properties
of vertices (such as the concept of share [13] or the common technique used in
the proof of Theorem 2.2). However, in order to deal with the special type of
codewords $c$, we develop a new technique of more global nature. For this
purpose, we first present the following lemma on a forbidden pattern of non-
codewords.

###### Lemma 2.7

Let $G=(V,E)$ be the king grid and $C\subseteq V$ be a solid-locating-
dominating code in $G$. Then
$T=\\{(i,j),(i,j+1),(i,j+2),(i+1,j+2),(i-1,j+2)\\}$ and any formation obtained
from $T$ by a rotation of $\pi/2$, $\pi$ or $3\pi/2$ radians around the origin
contains a codeword of $C$.

###### Proof 2.8

Assume that the set $T=\\{(i,j),(i,j+1),(i,j+2),(i+1,j+2),(i-1,j+2)\\}$
contains no codewords of $C$. Then a contradiction with the definition follows
since $I(i,j+1)\setminus I(i,j)=\emptyset$. The other cases obtained from $T$
by a rotation are proved analogously.

In the following theorem, we prove that the solid-locating-dominating code of
Theorem 2.5 is optimal, i.e., there is no code with density smaller than
$1/3$. The proof is based on the idea of studying one-way infinite strips of
vertices of width $3$ and showing that the density of codewords in these
strips is at least $1/3$.

###### Theorem 2.9

If $G=(V,E)$ is the king grid and $C\subseteq V$ is a solid-locating-
dominating code in $G$, then the density $D(C)\geq\frac{1}{3}$.

###### Proof 2.10

Let $S^{j}$ be a subgraph of $G$ induced by the vertex set
$V^{\prime}_{j}=\left\\{(x,y)\mid 1\leq x\leq 3,1\leq y\leq j\right\\}$.
Recall first the definition $V_{n}=\\{(x,y)\mid|x|\leq n,|y|\leq n\\}$.
Observe now that we may fit into the first quadrant $\\{(x,y)\mid 1\leq x\leq
n,1\leq y\leq n\\}$ of $V_{n}$ $\lfloor n/3\rfloor$ graphs isomorphic to
$S^{n}$. Similarly, the other three quadrants of $V_{n}$ can each contain
$\lfloor n/3\rfloor$ graphs isomorphic to $S^{n}$. Thus, in total, $4\lfloor
n/3\rfloor$ graphs isomorphic to $S_{n}$ can be fitted into $V_{n}$.

Let $C$ be a solid-locating-dominating code in $G$. In the final part of the
proof, we show that any subgraph of $G$ isomorphic to $S^{n}$ contains at
least $n-3$ codewords. Assuming this is the case, the density of $C$ can be
estimated as follows:

$D(C)=\limsup_{n\rightarrow\infty}\frac{|C\cap
V_{n}|}{|V_{n}|}\geq\limsup_{n\rightarrow\infty}\frac{4\lfloor\frac{n}{3}\rfloor\cdot(n-3)}{(2n+1)^{2}}\geq\limsup_{n\rightarrow\infty}\frac{4(n-3)^{2}}{3(2n+1)^{2}}=\frac{1}{3}\text{.}$

It remains to be shown that any subgraph of $G$ isomorphic to $S^{n}$ contains
at least $n-3$ codewords. By symmetry, it is enough to show that $|C\cap
V^{\prime}_{n}|\geq n-3$. In what follows, we consider more closely the number
of codewords in a row $S_{i}=\\{(j,i)\mid 1\leq j\leq 3\\}$ of
$V^{\prime}_{n}$. For this purpose, the following set of rules for rearranging
the codewords inside $V^{\prime}_{n}$ are introduced:

  * Rule $1.1$:

If $S_{i}\cap C=\emptyset$, $1\leq i\leq n-1$ and
$\\{(1,i+1),(3,i+1)\\}\subseteq C$, then one codeword is moved from $S_{i+1}$
to $S_{i}$. The rule is illustrated in Figure 6.

  * Rule $1.2$:

If $S_{i}\cap C=\emptyset$, $2\leq i$ and $\\{(1,i-1),(3,i-1)\\}\subseteq C$,
then one codeword is moved from $S_{i-1}$ to $S_{i}$. The rule can be viewed
as a reflected version of Rule 1.1.

  * Rule $2.1$:

If $S_{i}\cap C=\emptyset$, $2\leq i$ and $\\{(1,i-1),(2,i-1)\\}=C\cap
S_{i-1}$, then one codeword is moved from $S_{i-1}$ to $S_{i}$. The rule is
illustrated in Figure 6.

  * Rule $2.2$:

If $S_{i}\cap C=\emptyset$, $2\leq i$ and $\\{(2,i-1),(3,i-1)\\}=C\cap
S_{i-1}$, then one codeword is moved from $S_{i-1}$ to $S_{i}$. The rule can
be viewed as a reflected version of Rule 2.1.

  * Rule $3.1$:

If $S_{i}\cap C=\emptyset$, $3\leq i$, $S_{i-1}\cap C=\\{(1,i-1)\\}$ and
$\\{(2,i-2),(3,i-2)\\}\subseteq S_{i-2}\cap C$, then one codeword is moved
from $S_{i-2}$ to $S_{i}$. The rule is illustrated in Figure 6.

  * Rule $3.2$:

If $S_{i}\cap C=\emptyset$, $3\leq i$, $S_{i-1}\cap C=\\{(3,i-1)\\}$ and
$\\{(2,i-2),(1,i-2)\\}\subseteq S_{i-2}\cap C$, then one codeword is moved
from $S_{i-2}$ to $S_{i}$. The rule can be viewed as a reflected version of
Rule 3.1.

  * Rule $4.1$:

If $S_{i}\cap C=\emptyset$, $3\leq i$, $S_{i-1}\cap C=\\{(1,i-1)\\}$ and
$\\{(1,i-2),(2,i-2)\\}=S_{i-2}\cap C$, then one codeword is moved from
$S_{i-2}$ to $S_{i}$. The rule is illustrated in Figure 6.

  * Rule $4.2$:

If $S_{i}\cap C=\emptyset$, $3\leq i$, $S_{i-1}\cap C=\\{(3,i-1)\\}$ and
$\\{(2,i-2),(3,i-2)\\}=S_{i-2}\cap C$, then one codeword is moved from
$S_{i-2}$ to $S_{i}$. The rule can be viewed as a reflected version of Rule
4.1.

$X$ $?$ $X$ Figure 3:
Rule $1.1$

$X$ $X$ Figure 4:
Rule $2.1$

$X$ $?$ $X$ $X$ Figure 5:
Rule $3.1$

$X$ $X$ $X$ Figure 6:
Rule $4.1$

Denote the code obtained after simultaneously applying the previous rules by
$C^{\prime}$. Notice that the rearrangement $C^{\prime}$ of $C$ is not
completely determined by the previous rules and that this is not actually
needed as in the following we are only interested on the number of codewords
in the rows of $V^{\prime}_{n}$. In other words, when a codeword is moved from
a row we can choose any of the codewords and move it to replace any non-
codeword of the target row. In what follows, we show that each row which has
given away codewords still contains at least one and each row which originally
did not contain any codeword has received at least one except possibly the
rows $S_{1}$, $S_{2}$ and $S_{n}$.

We immediately notice that the rules move codewords only from the rows with at
least two codewords. Each type of row with at least two codewords is examined
as follows:

  * •

$C\cap S_{i}=\\{(j,i)\mid 1\leq j\leq 3\\}$: Rules $1.1,1.2,3.1$ and $3.2$ can
be applied on rows with three codewords. Among these, Rules $3.1$ and $3.2$
cannot be applied at the same time and Rule $1.2$ cannot be applied together
with Rules $3.1$ or $3.2$. Hence, we apply at most two rules on a row with
three codewords and that row has at least one codeword left in the code
$C^{\prime}$.

  * •

$C\cap S_{i}=\\{(j,i)\mid 1\leq j\leq 2\\}$: Rules $2.1,3.2$ and $4.1$ can be
applied on this types of rows. We cannot apply Rule $2.1$ at the same time as
$3.2$ or $4.1$ since $2.1$ requires that $S_{i+1}\cap C=\emptyset$ and Rules
$3.2$ and $4.1$ require that $|S_{i+1}\cap C|=1$. Furthermore, we cannot apply
Rules $3.2$ and $4.1$ at the same time since they require the codeword on the
row $S_{i+1}$ to locate at different places. Hence, $C^{\prime}$ is left with
at least one codeword.

  * •

$C\cap S_{i}=\\{(j,i)\mid 2\leq j\leq 3\\}$: This case is symmetrical to the
previous one (now the rules to be considered are 2.2, 3.1 and 4.2).

  * •

$C\cap S_{i}=\\{(j,i)\mid j\neq 2\\}$: We can only apply Rules $1.1$ and $1.2$
on these types of rows and both of them only when $i\geq 2$. However, if both
of the rules are used, then $C\cap S_{i-1}=C\cap S_{i+1}=\emptyset$ and a
contradiction with Lemma 2.7 follows. Hence, at most one rule is used and
$|C^{\prime}\cap S_{i}|\geq 1$.

Let us then show that we have $|C^{\prime}\cap S_{i}|\geq 1$ for each $i$ such
that $C\cap S_{i}=\emptyset$ and $3\leq i\leq n-1$. In the following cases, we
assume that $S_{i}\cap C=\emptyset$ and the cases are categorized by
considering the different formations of the row $S_{i-1}$.

  * •

$S_{i-1}\cap C=\emptyset$: Considering different orientations and positions of
the formation $T$ in Lemma 2.7, we have $S_{i+1}\subseteq C$. Hence, due to
Rule $1.1$, one codeword from $S_{i+1}$ is moved to $S_{i}$ and we obtain
$|C^{\prime}\cap S_{i}|\geq 1$.

  * •

$S_{i-1}\cap C=\\{(1,i-1)\\}$: By Lemma 2.7, we have $(2,i-2)\in C$. Notice
that if $(1,i-2)$ and $(3,i-2)$ do not belong to $C$, then a contradiction
with the definition of solid-locating-dominating codes follows since we have
$I(2,i-1)\subseteq I(1,i-2)$ for non-codewords $(2,i-1)$ and $(1,i-2)$. Hence,
at least one of the vertices $(1,i-2)$ and $(3,i-2)$ belongs to $C$.
Therefore, either Rule $3.1$ or $4.1$ can be applied (to the row $S_{i-2}$)
and we have $|C^{\prime}\cap S_{i}|\geq 1$.

  * •

$S_{i-1}\cap C=\\{(3,i-1)\\}$: This case is symmetrical to the previous one.
Here we just use either Rule $3.2$ or $4.2$.

  * •

$S_{i-1}\cap C=\\{(2,i-1)\\}$: By Lemma 2.7, we have
$\\{(1,i+1),(3,i+1)\\}\subseteq C$. Hence, due to Rule $1.1$, we have
$|C^{\prime}\cap S_{i}|\geq 1$.

  * •

$S_{i-1}\cap C=\\{(1,i-1),(2,i-1)\\}$: Due to Rule $2.1$, we have
$|C^{\prime}\cap S_{i}|\geq 1$.

  * •

$S_{i-1}\cap C=\\{(2,i-1),(3,i-1)\\}$: Due to Rule $2.2$, we have
$|C^{\prime}\cap S_{i}|\geq 1$.

  * •

$S_{i-1}\cap C=\\{(1,i-1),(3,i-1)\\}$: Due to Rule $1.2$, we have
$|C^{\prime}\cap S_{i}|\geq 1$.

  * •

$S_{i-1}\cap C=\\{(1,i-1),(2,i-1),(3,i-1)\\}$: Due to Rule $1.2$, we have
$|C^{\prime}\cap S_{i}|\geq 1$.

Thus, in conclusion, we have shown that for $3\leq i\leq n-1$ we have
$|C^{\prime}\cap S_{i}|\geq 1$. Therefore, as the rules rearrange codewords
only inside $V^{\prime}_{n}$, we have $|C\cap
V^{\prime}_{n}|\geq|C^{\prime}\cap V^{\prime}_{n}|\geq n-3$. This concludes
the proof of the lower bound $D(C)\geq 1/3$.

In the previous theorems, we have shown that the density of an optimal solid-
locating-dominating code in the king grid is $1/3$. Recall that a self-
locating-dominating code is always solid-locating-dominating. Hence, by the
previous lower bound, we also know that there exists no self-locating-
dominating code in the king grid with density smaller than $1/3$. However, the
construction given for the solid-location-domination does not work for self-
location-domination. For example, we have $I(2,0)=\\{(2,-1),(2,1),(3,0)\\}$
and $N[(2,-1)]\cap N[(2,1)]\cap N[(3,0)]=\\{(2,0),(3,0)\\}$ contradicting with
the definition of self-locating-dominating codes (see Figure 2). In the
following theorem, we present a self-locating-dominating code in the king grid
with the density $1/3$. Notice that this code is also solid-locating-
dominating.

###### Theorem 2.11

Let $G=(V,E)$ be the king grid. The code

$C=\left\\{(x,y)\in\mathbb{Z}^{2}\mid x-y\equiv 0\pmod{3}\right\\}$

is self-locating-dominating in $G$ and its density is $1/3$.

###### Proof 2.12

The density $D(C)=1/3$ since in each row every third vertex is a codeword.
Furthermore, $C$ is a self-locating-dominating code since each non-codeword
$v$ is covered either by the set of three codewords
$\\{v+(1,0),v+(0,-1),v+(-1,1)\\}$ or $\\{v+(-1,0),v+(0,1),v+(1,-1)\\}$, and in
both cases the closed neighbourhoods of the codewords intersect uniquely in
the vertex $v$.

##  3 Direct product of complete graphs

A graph is called a _complete graph_ on $q$ vertices, denoted by $K_{q}$, if
each pair of vertices of the graph is adjacent. The vertex set $V(K_{q})$ is
denoted by $\\{1,2,\ldots,q\\}$. The _Cartesian product_ of two graphs
$G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ is defined as $G_{1}\square
G_{2}=(V_{1}\times V_{2},E)$, where $E$ is a set of edges such that
$(u_{1},u_{2})(v_{1},v_{2})\in E$ if and only if $u_{1}=v_{1}$ and
$u_{2}v_{2}\in E_{2}$, or $u_{2}=v_{2}$ and $u_{1}v_{1}\in E_{1}$. The _direct
product_ of two graphs $G_{1}$ and $G_{2}$ is defined as $G_{1}\times
G_{2}=(V_{1}\times V_{2},E)$, where $E=\\{(u_{1},u_{2})(v_{v},v_{2})\mid
u_{1}v_{1}\in E_{1}\text{ and }u_{2}v_{2}\in E_{2}\\}$. A _complement_ of a
graph $G=(V,E)$ is the graph $\overline{G}=(V,E^{\prime})$ with the edge set
$E^{\prime}$ being such that $uv\in E^{\prime}$ if and only if $uv\notin E$.

In this section, we give optimal locating-dominating, self-locating-dominating
and solid-locating-dominating codes in the direct product $K_{n}\times K_{m}$,
where $2\leq n\leq m$. For location-domination and solid-location-domination,
the results heavily depend on the exact values of $\gamma^{LD}(K_{n}\square
K_{m})$ and $\gamma^{DLD}(K_{n}\square K_{m})$, which have been determined in
[10]. In the graphs $K_{n}\times K_{m}$ and $K_{n}\square K_{m}$, the $j$th
_row_ (of $V(K_{n})\times V(K_{m})$) is denoted by $R_{j}$ and it consists of
the vertices $(1,j),(2,j),\ldots,(n,j)$. Analogously, the $i$th _column_ is
denoted by $P_{i}$ and it consists of the vertices $(i,1),(i,2),\ldots,(i,m)$.
Now we are ready to present the following observations:

  * •

In the Cartesian product $K_{n}\square K_{m}$, the closed neighbourhood
$N[(i,j)]=N[i,j]$ consists of the row $R_{j}$ and the column $P_{i}$.
Therefore, as the closed neighbourhood of a vertex resembles the movements of
a rook in a chessboard, $K_{n}\square K_{m}$ is also sometimes called the
_rook’s graph_.

  * •

In the direct product $K_{n}\times K_{m}$, we have
$N((i,j))=N(i,j)=V(K_{n}\square K_{m})\setminus(R_{j}\cup P_{i})$.

Due to the previous observations, we know that $\overline{K_{n}\square
K_{m}}=K_{n}\times K_{m}$.

Recall that identification is a topic closely related to the various location-
domination type problems. Previously, in [14], the identifying codes have been
studied in the direct product $K_{n}\times K_{m}$ of complete graphs by
Goddard and Wash. More precisely, they determined the exact values of
$\gamma^{ID}(K_{n}\times K_{m})$ for all $m$ and $n$.

In what follows, we determine the exact values of $\gamma^{LD}(K_{n}\times
K_{m})$ for all $m$ and $n$. For this purpose, we first present the following
result concerning location-domination in the Cartesian product $K_{n}\square
K_{m}$ of complete graphs given in [10].

######  Theorem 3.1 ([10], Theorem 14)

Let $m$ and $n$ be integers such that $2\leq n\leq m$. Now we have

$\gamma^{LD}(K_{n}\square K_{m})=\begin{cases}m-1,&2n\leq
m,\cr\left\lceil\frac{2n+2m}{3}\right\rceil-1,&n\leq m\leq 2n-1.\end{cases}$

There is a strong connection between the values of $\gamma^{LD}(K_{n}\square
K_{m})$ and $\gamma^{LD}(K_{n}\times K_{m})$ as explained in the following. In
[15], it has been shown that $|\gamma^{LD}(G)-\gamma^{LD}(\overline{G})|\leq
1$. Therefore, as $\overline{K_{n}\times K_{m}}=K_{n}\square K_{m}$, we obtain
that $\gamma^{LD}(K_{n}\square K_{m})-1\leq\gamma^{LD}(K_{n}\times
K_{m})\leq\gamma^{LD}(K_{n}\square K_{m})+1$. This result is further sharpened
in the following lemma.

###### Lemma 3.2

For $2\leq n\leq m$ and $(n,m)\neq(2,4)$, we have

$\gamma^{LD}(K_{n}\square K_{m})-1\leq\gamma^{LD}(K_{n}\times
K_{m})\leq\gamma^{LD}(K_{n}\square K_{m}).$

If $\gamma^{LD}(K_{n}\times K_{m})=\gamma^{LD}(K_{n}\square K_{m})-1$, then
the optimal locating-dominating code $C$ in $K_{n}\times K_{m}$ has a non-
codeword $v$ such that $I(v)=C$.

###### Proof 3.3

First denote $G=K_{n}\square K_{m}$ and $H=K_{n}\times K_{m}$. The lower bound
of the claim is immediate by the result preceding the lemma. For the upper
bound, let $C$ be an optimal locating-dominating code in $G$. The code $C$ can
also be viewed as a code in $H$. If we have $I(H;u)=I(H;v)$ for some non-
codewords $u$ and $v$, then a contradiction follows since $I(G;u)=C\setminus
I(H;u)=C\setminus I(H;v)=I(G;v)$. Hence, we have $I(H;u)\neq I(H;v)$ for all
distinct non-codewords $u$ and $v$. Moreover, if $I(G;v)\neq C$ for each non-
codeword $v$, then we also have $I(H;v)\neq\emptyset$, and the upper bound
follows since $C$ is a locating-dominating code in $H$.

Hence, we may assume that $I(G;v)=C$ for some non-codeword $v$. This implies
that $C\subseteq P_{i}\cup R_{j}$ for some $i,j$. There exists at most one
non-codeword in $P_{i}\setminus\\{v\\}$ since otherwise there are at least two
non-codewords with the same $I$-set. Similarly, there exists at most one non-
codeword in $R_{j}\setminus\\{v\\}$. Furthermore, if both
$P_{i}\setminus\\{v\\}$ and $R_{j}\setminus\\{v\\}$ contain a non-codeword,
then there exists a vertex with an empty $I$-set. Thus, in conclusion, there
exists at most two non-codewords in $P_{i}\cup R_{j}$ and, hence, we have
$|C|\geq n+m-3$. Dividing into the following cases depending on $n$ and $m$,
we next show that $|C|\geq n+m-3>\gamma^{LD}(G)$ in majority of the cases of
the lemma:

  * •

If $n\geq 3$ and $m\geq 2n$, then we have $\gamma^{LD}(G)=m-1<n+m-3\leq|C|$
(by Theorem 3.1).

  * •

If $n\geq 4$, $n\leq m\leq 2n-1$ and $(n,m)\neq(4,4)$, then
$\gamma^{LD}(G)=\lceil 2(n+m)/3\rceil-1<n+m-3\leq|C|$ (by Theorem 3.1).

Thus, if $n\geq 3$ and $m\geq 2n$, or $n\geq 4$, $n\leq m\leq 2n-1$ and
$(n,m)\neq(4,4)$, then a contradiction with the optimality of $C$ follows.
Hence, in these cases, we have $\gamma^{LD}(H)\leq\gamma^{LD}(G)$.

The rest of the cases are covered in the following:

  * •

If $n=2$ and $2\leq m\leq 3$, then $C=P_{1}$ is an optimal locating-dominating
code in $G$ with the property that for any non-codeword $v$ we have
$I(G;v)\neq C$. Similarly, if $n=2$ and $m\geq 5$, then
$C=\\{(2,1),(2,2)\\}\cup P_{1}\setminus\\{(1,i)\mid i\leq 3\\}$ is an optimal
locating-dominating code in $G$ with the property that for no vertex $v$ we
have $I(G;v)=C$. Thus, in both cases, the code $C$ is also locating-dominating
in $H$ by the first paragraph of the proof.

  * •

If $n=m=3$, then $C=\\{(1,1),(1,2),(2,1)\\}$ is a locating-dominating code in
$H$ with $\gamma^{LD}(G)=3$ codewords.

  * •

If $n=3$ and $4\leq m\leq 5$ or $(n,m)=(4,4)$, then
$\\{(1,1),(1,3),(2,2),(2,4)\\}$,
$\\{(1,1),(1,3),\linebreak(2,2),(2,4),(3,5)\\}$ and
$\\{(1,1),(1,3),(2,2),(2,4),(3,1)\\}$ obtained from the proof of [10, Theorem
14] are optimal locating-dominating codes in $K_{3}\square K_{4}$,
$K_{3}\square K_{5}$ and $K_{4}\square K_{4}$, respectively. Therefore, since
there does not exist a non-codeword covering all the codewords (in the
Cartesian product) in any of the cases, the codes are also locating-dominating
in $K_{3}\times K_{4}$, $K_{3}\times K_{5}$ and $K_{4}\times K_{4}$ (by the
first paragraph of the proof), respectively.

Let then $C^{\prime}$ be a locating-dominating code in $H$. Similarly as
above, we get that if $I(H;v)\neq C^{\prime}$ for each non-codeword $v$, then
$C^{\prime}$ is also a locating-dominating code in $G$. Therefore, if
$\gamma^{LD}(H)=\gamma^{LD}(G)-1$, then there exist a non-codeword $v$ such
that $I(H;v)=C^{\prime}$. Thus, the last claim of the lemma follows.

Now with the help of the previous lemma and Theorem 3.1, we determine the
exact values of $\gamma^{LD}(K_{m}\times K_{n})$ in the following theorem.

$B_{1}$ $B_{1}$ $B_{1}$ $B_{1}$ $B_{1}$ $B_{1}$ $B_{1}$ $B_{1}$ $B_{1}$
$B_{1}$ $B_{1}$ $B_{1}$ $B_{2}$ $B_{2}$ $B_{1}B_{2}$ $B_{1}B_{2}$ $B_{1}B_{2}$
$B_{2}$ $B_{2}$ $B_{2}$ $B_{2}$ $B_{1}B_{2}$ $B_{1}B_{2}$ $B_{1}B_{2}$ $B_{2}$
$B_{2}$ $B_{2}$ $B_{2}$ $B_{1}B_{2}$ $B_{1}B_{2}$ $B_{1}B_{2}$ $B_{2}$ $B_{2}$
Figure 7: Optimal locating-dominating code for $K_{10}\times K_{10}$. Dark
boxes are codewords.

###### Theorem 3.4

For $2\leq n\leq m$ we have

$\gamma^{LD}(K_{n}\times K_{m})=\begin{cases}m-1,&2n\leq m\text{ and
}(n,m)\neq(2,4),\\\ \left\lceil\frac{2n+2m-1}{3}\right\rceil-1,&2<n\leq
m<2n\text{ and }(m,n)\neq(4,4)\\\ m,&n=2,m\leq 4,\\\ 5,&n=4,m=4.\end{cases}$

###### Proof 3.5

Let $C$ be a locating-dominating code in $K_{n}\times K_{m}$. We cannot have
$R_{i}\cap C=R_{j}\cap C=\emptyset$ for $i\neq j$ since otherwise, for
example, $I(C;(1,i))=I(C;(1,j))$. Similarly, there exists at most one column
without codewords of $C$. Thus, we have $\gamma^{LD}(K_{n}\times K_{m})\geq
m-1$. Therefore, if $m\geq 2n$ and $(n,m)\neq(2,4)$, then by the previous
lemma we have $m-1\leq\gamma^{LD}(K_{n}\times
K_{m})\leq\gamma^{LD}(K_{n}\square K_{m})=m-1$, i.e., $\gamma^{LD}(K_{n}\times
K_{m})=m-1$.

Assume then that $2<n\leq m\leq 2n-1$ and $n+m\equiv 0,1\\!\pmod{3}$. In what
follows, we show that now $|C|\geq\gamma^{LD}(K_{n}\square K_{m})$. By the
previous lemma, we know that if there is no non-codeword $u$ such that
$I(K_{n}\times K_{m},C;u)=C$, i.e., there does not exist a row and column
without codewords, then $|C|=\gamma^{LD}(K_{n}\square K_{m})$. Hence, we may
now assume that there exist a row and a column without codewords. Without loss
of generality, we may assume that they are $P_{n}$ and $R_{m}$. Observe that
$C$ can now also be viewed as a code in $K_{n-1}\square K_{m-1}$ and that $C$
is locating-dominating in $K_{n-1}\square K_{m-1}$ with the following
additional properties: (i) each column has at least one codeword, (ii) each
row has at least one codeword and (iii) no codeword $(i,j)\in C$ is such that
$(P_{i}\cup R_{j})\cap C=\\{(i,j)\\}$, i.e., no codeword of $C$ is isolated.
Indeed, the properties (i) and (ii) follow immediately by the first paragraph
of the proof and if $(i,j)\in C$ is a codeword violating the property (iii),
then we have $I(K_{n}\times K_{m},(n,j))=I(K_{n}\times
K_{m};(i,m))=C\setminus\\{(i,j)\\}$ (a contradiction). Now we are ready to
prove a lower bound on $|C|$ as in [10, Theorem 14]. Denote the number of
columns and rows with exactly one codeword in $K_{n}\square K_{m}$ by $s_{p}$
and $s_{r}$, respectively. Now we obtain that $|C|\geq
s_{p}+2(n-1-s_{p})=2(n-1)-s_{p}$ and $|C|\geq s_{r}+2(m-1-s_{r})=2(m-1)-s_{r}$
(by the properties (i) and (ii)). This further implies that $s_{p}\geq
2(n-1)-|C|$ and $s_{r}\geq 2(m-1)-|C|$. By the property (iii), we now obtain
that $|C|\geq s_{p}+s_{r}\geq 2(n-1)+2(m-1)-2|C|$. Thus, we have
$|C|\geq\left\lceil(2m+2n-1)/3\right\rceil-1$. Hence, as $n+m\equiv
0,1\\!\pmod{3}$, we have
$|C|\geq\left\lceil(2m+2n-1)/3\right\rceil-1=\left\lceil(2m+2n)/3\right\rceil-1=\gamma^{LD}(K_{n}\square
K_{m})$. Thus, by the upper bound of the previous lemma, we obtain that
$\gamma^{LD}(K_{n}\times K_{m})=\gamma^{LD}(K_{n}\square K_{m})$ if $2<n\leq
m\leq 2n-1$ and $n+m\equiv 0,1\\!\pmod{3}$.

Assume then that $2<n\leq m\leq 2n-1$, $n+m\equiv 2\\!\pmod{3}$ and
$(n,m)\neq(4,4)$. In what follows, we show that the lower bound of Lemma 3.2
is attained, i.e., $\gamma^{LD}(K_{n}\times K_{m})=\gamma^{LD}(K_{n}\square
K_{m})-1$. Denote $n^{\prime}=n-1$ and $m^{\prime}=m-1$ and observe that
$n^{\prime}+m^{\prime}$ is divisible by three. Let $C^{\prime}=A_{1}\cup
A_{2}\cup A_{3}$ be a code in $K_{n}\times K_{m}$ with

$\displaystyle A_{1}$ $\displaystyle=\left\\{(i,i)\mid 1\leq
i\leq\frac{n^{\prime}+m^{\prime}}{3}\right\\},$ $\displaystyle A_{2}$
$\displaystyle=\left\\{(j,i)\mid\frac{n^{\prime}+m^{\prime}}{3}+1\leq i\leq
m^{\prime},j=2\frac{n^{\prime}+m^{\prime}}{3}+1-i\right\\}\text{ and }$
$\displaystyle A_{3}$ $\displaystyle=\left\\{(j,i)\mid 1\leq
i\leq\frac{2n^{\prime}-m^{\prime}}{3},j=i+\frac{n^{\prime}+m^{\prime}}{3}\right\\}.$

The code $C^{\prime}$ is illustrated in Figure 7. By straightforward counting
, we get
$|C^{\prime}|=|A_{1}|+|A_{2}|+|A_{3}|=m^{\prime}+\frac{2n^{\prime}-m^{\prime}}{3}=\frac{2n^{\prime}+2m^{\prime}}{3}=\frac{2n+2m-1}{3}-1=\gamma^{LD}(K_{n}\square
K_{m})-1$. In what follows, we first show that $C^{\prime}$ is almost a
locating-dominating code in $K_{n}\square K_{m}$ with the exception that
$I(C^{\prime};(n,m))=\emptyset$.

Denote the sets of non-codewords $(j,i)$ with
$(2n^{\prime}+2m^{\prime})/3-m^{\prime}+1\leq j\leq(n^{\prime}+m^{\prime})/3$
and $i\leq(2n^{\prime}+2m^{\prime})/3-m^{\prime}$ by $B_{1}$ and $B_{2}$,
respectively. It is straightforward to verify that each non-codeword $u\in
B_{1}\cup B_{2}$ has at least three codewords in $I(K_{n}\square
K_{m},C^{\prime};u)$ and the codewords of $I(K_{n}\square K_{m},C^{\prime};u)$
do not lie on a single row or column. This implies that $\bigcap_{c\in
I(C^{\prime};u)}N[c]=\\{u\\}$ for any $u\in B_{1}\cup B_{2}$, i.e., there is
no other vertex containing $I(C^{\prime};u)$ in its $I$-set. Thus, each non-
codeword in $B_{1}\cup B_{2}$ has a unique nonempty $I$-set. Consider then a
non-codeword $v=(j,i)$ with $i>(2n^{\prime}+2m^{\prime})/3-m^{\prime}$ and
$j<(2n^{\prime}+2m^{\prime})/3-m+1^{\prime}$. By the construction of
$C^{\prime}$, we have $|I(C^{\prime};v)|=2$. Now there exists a codeword
$(j,j)\in I(v)$ since $j\leq(2n^{\prime}+2m^{\prime})/3-m^{\prime}$.
Furthermore, there exists a codeword $c\in I(j,j)\cap A_{3}$. Hence, if there
exists a non-codeword $w$ such that $I(C^{\prime};v)=I(C^{\prime};w)$, then
$w\in B_{2}$ and a contradiction follows as $|I(C^{\prime};w)|\geq 3$. Thus,
the $I$-set of $v$ is nonempty and unique. Similarly, it can be shown that
$I(C^{\prime};(j,i))$ is nonempty and unique for
$i>(2n^{\prime}+2m^{\prime})/3-m^{\prime}$ and $j>(n^{\prime}+m^{\prime})/3$.

Consider then non-codewords $u=(j,m)$ and $v=(n,i)$ with $1\leq j\leq n-1$ and
$1\leq i\leq m-1$. We immediately obtain that $I(C^{\prime};(j,m))=P_{j}\cap
C^{\prime}$ and $I(C^{\prime};(n,i))=R_{i}\cap C^{\prime}$. These $I$-sets are
nonempty since each row and column contains a codeword. These $I$-sets are
also different from the ones of non-codewords inside $K_{n^{\prime}}\square
K_{m^{\prime}}$ which contain at least two codewords in different rows and
columns. It is also impossible to have $I(C^{\prime};u)=I(C^{\prime};v)$ since
each codeword has another one in the same row or column. Thus, $u$ and $v$
have nonempty and unique $I$-sets. Thus, in conclusion, we have shown that
$I(C^{\prime};u)$ is nonempty and unique for all non-codewords $u$ in
$K_{n}\square K_{m}$ except $(n,m)$ (for which we have
$I(C^{\prime};(n,m))=\emptyset$). Furthermore, there does not exist a non-
codeword $v$ such that $I(C^{\prime};v)=C^{\prime}$. Therefore, as in the
proof of Lemma 3.2, we obtain that $C^{\prime}$ is a locating-dominating code
in $K_{n}\times K_{m}$. Thus, we have $\gamma^{LD}(K_{n}\times
K_{m})=\gamma^{LD}(K_{n}\square K_{m})-1$.

Now majority of the cases have been considered, and we only have some special
cases left. Concluding the proof, these cases are solved as follows:

  * •

Assume that $n=2$ and $m\leq 4$. It is easy to see that $C=P_{1}$ is a
locating-dominating code in $K_{n}\times K_{m}$. For the lower bound, first
recall that $K_{n}\times K_{m}$ has at most one row without codewords (by the
first paragraph of the proof). Therefore, if $C$ is a locating-dominating code
in $K_{n}\times K_{m}$ with $|C|\leq m-1$, then all the codewords lie on
different rows. Hence, in all the cases, there exist a non-codeword with an
empty $I$-set. Thus, we have $\gamma^{LD}(K_{n}\times K_{m})=m$.

  * •

Assume that $n=m=4$. By Lemma 3.2, we immediately have
$4\leq\gamma^{LD}(K_{4}\times K_{4})\leq 5$. Let $C$ be a locating-dominating
code in $K_{4}\times K_{4}$. As in the second paragraph of the proof, it can
be shown that either $|C|\geq\gamma^{LD}(K_{4}\square K_{4})=5$ (and we are
done), or $C$ is locating-dominating in $K_{3}\times K_{3}$ with the
additional properties (i), (ii) and (iii). In the latter case, due to (i),
(ii) and (iii), there exist a row and a column of $K_{3}\times K_{3}$ with two
codewords such that their intersection is a non-codeword $u$. Hence, a
contradiction follows since $I(K_{4}\times K_{4},C;u)=\emptyset$. Thus, we
have $\gamma^{LD}(K_{4}\times K_{4})=5$.

Let us next briefly consider solid-location-domination. The following result
has been shown in [10].

######  Theorem 3.6 ([10])

For all integers $m$ and $n$ such that $m\geq n\geq 1$, we have

$\gamma^{DLD}(K_{n}\square K_{m})=\begin{cases}m,&4\leq 2n\leq m\textnormal{
or }n=2,\cr 2n,&2<n<m<2n,\cr 2n-1,&2<m=n.\end{cases}$

In the following theorem, we show that the cardinalities of optimal solid-
locating-dominating codes are same for $K_{n}\times K_{m}$ and $K_{n}\square
K_{m}$.

###### Theorem 3.7

For all integers $m$ and $n$ such that $m\geq n\geq 2$, we have

$\gamma^{DLD}(K_{n}\times K_{m})=\gamma^{DLD}(K_{n}\square K_{m}).$

###### Proof 3.8

By [12, Theorem 21], we have $\gamma^{DLD}(G)=\gamma^{DLD}(\overline{G})$ if
$G$ is not a discrete or a complete graph. Therefore, as this is the case for
$G=K_{n}\times K_{m}$, we have $\gamma^{DLD}(K_{n}\times
K_{m})=\gamma^{DLD}(\overline{K_{n}\times K_{m}})=\gamma^{DLD}(K_{n}\square
K_{m})$.

Let us then consider self-location-domination. Unlike location-domination [15,
Theorem 7] and solid-location-domination [12, Theorem 21], the optimal
cardinality of a self-locating-dominating code in $G$ does not depend on the
one of the complement graph $\overline{G}$. In the following theorem, we first
give the result presented in [10] regarding $\gamma^{SLD}(K_{n}\square
K_{m})$.

######  Theorem 3.9 ([10])

For all integers $m$ and $n$ such that $m\geq n\geq 2$, we have

$\gamma^{SLD}(K_{n}\square K_{m})=\begin{cases}m,&2n\leq m,\cr 2n,&2\leq
n<m<2n,\cr 2n-1,&2<m=n,\cr 4,&n=m=2.\end{cases}$

In the following theorem, we determine the exact values of
$\gamma^{SLD}(K_{n}\times K_{m})$ for all values of $m$ and $n$. Notice that
$\gamma^{SLD}(K_{n}\square K_{m})=\gamma^{SLD}(K_{n}\times K_{m})$ if and only
if $n=m$, $m=n+1>3$, or $n=2$ and $m\geq 4$.

###### Theorem 3.10

For all integers $m$ and $n$ such that $m\geq n\geq 2$, we have

$\gamma^{SLD}(K_{n}\times K_{m})=\begin{cases}m+n-1,&n>2,\\\ m,&n=2,m>2,\\\
4,&n=m=2.\end{cases}$

###### Proof 3.11

Let $C$ be a self-locating-dominating code in $K_{n}\times K_{m}$. Notice
first that if $n=m=2$, then $K_{2}\times K_{2}$ is isomorphic to a forest of
two paths of length two and, therefore, $\gamma^{SLD}(K_{2}\times K_{2})=4$.
Hence, we may assume that $(n,m)\neq(2,2)$. Observe then that if a column
$P_{i}$ contains no codewords, i.e., $P_{i}\cap C=\emptyset$, then
$C=V\setminus P_{i}$. Indeed, for any vertices $(i,j)\in P_{i}$ and $(h,j)\in
V$ with $i\neq h$, we have $I(h,j)\subseteq I(i,j)$ and the claim
$C=V\setminus P_{i}$ follows by Theorem 1.4. Analogously, it can be shown that
if $R_{i}\cap C=\emptyset$, then $C=V\setminus R_{i}$. Suppose now that $n=2$
and $m>2$. If each row contains a codeword, then we immediately have $|C|\geq
m$. Otherwise, there exists a row without codewords and, by the previous
observation, we have $|C|\geq 2m-2\geq m$. Hence, we obtain that $|C|\geq m$.
Furthermore, $P_{1}$ is a self-locating-dominating code in $K_{2}\times K_{m}$
with $m$ codewords. Thus, in conclusion, we have $\gamma^{SLD}(K_{2}\times
K_{m})=m$.

Assume that $n>2$. By the previous observations, we know that if there exists
a row or a column without codewords, then $|C|\geq\min\\{mn-m,mn-n\\}=mn-m\geq
m+n-1$. Hence, we may assume that each row and column contains a codeword of
$C$. Furthermore, if each row contains at least $2$ codewords, then $|C|\geq
2m\geq m+n-1$. Hence, we may assume that there exists a row $R_{i}$ with
exactly one codeword, i.e., $R_{i}\cap C=\\{(j,i)\\}$ for some $j$. Hence, as
$I(j,h)\subseteq I(j,i)$ for any $h\neq i$, we have $P_{j}\subseteq C$.
Therefore, as each column different from $P_{j}$ also contains a codeword, we
obtain that $|C|\geq m+n-1$. Thus, we have $\gamma^{SLD}(K_{n}\times
K_{m})\geq m+n-1$. Finally, this lower bound can be attained with a code
$C^{\prime}=\\{(i,j)\mid i=1\text{ or }j=1\\}$. Indeed, for any $i,j>1$, we
have $I(1,1)=\\{(1,1)\\}$,
$I(1,j)=\\{(1,j)\\}\cup(R_{1}\setminus\\{(1,1)\\})$,
$I(j,1)=\\{(j,1)\\}\cup(P_{1}\setminus\\{(1,1)\\})$ and
$I(i,j)=C^{\prime}\setminus\\{(1,j),(i,1)\\}$. Therefore, we have
$I(v)\not\subseteq I(u)$ for any vertex $u$ and non-codeword $v$. Thus, by
Theorem 1.4, $C^{\prime}$ is a self-locating-dominating code in $K_{n}\times
K_{m}$, and we have $\gamma^{SLD}(K_{n}\times K_{m})=n+m-1$.

##  4 On certain type of Hamming graphs

The Cartesian product $K_{q}\square K_{q}\square\cdots\square K_{q}$ of $n$
copies of $K_{q}$ is denoted by $K_{q}^{n}$ and called a Hamming graph.
Goddard and Wash [16] studied identification in the case of $K_{q}^{n}$ and
they, in particular, bounded the cardinality of an optimal identifying code to
$q^{2}-q\sqrt{q}\leq\gamma^{ID}(K_{q}^{3})\leq q^{2}$. In [11], we further
improved this bound to $q^{2}-\frac{3}{2}q\leq\gamma^{ID}(K_{q}^{3})\leq
q^{2}-4^{t-1}$ where $2\cdot 4^{t}\leq q\leq 2\cdot 4^{t+1}-1$ or $q=4^{t}$,
and we also showed that $\gamma^{SLD}(K^{3}_{q})=q^{2}$. In this section, we
show that also $\gamma^{DLD}(K^{3}_{q})=q^{2}$.

The following lemma is presented as Exercise 1.12 in [17].

######  Lemma 4.1 ([17])

For each positive integer $q$, we have

$\gamma(K_{q}\square K_{q})=q.$

In the following we present some terminology and notations we use. More
information about them and their usefulness can be found in [11].

  * •

The pipe $P^{i}(a,b)\subseteq V(K_{q}^{3})$ is a set of vertices fixing all
but the $i$th coordinate which varies between $1$ and $q$. The fixed
coordinates are $a$ and $b$ where $a$ is the value of left fixed coordinate in
the representation $(x,y,z)$. For example $P^{3}(a,b)=\\{(a,b,i)\mid 1\leq
i\leq q\\}$.

  * •

The layer $L^{i}_{j}\subseteq V(K_{q}^{3})$ is a set of vertices fixing the
$i$th coordinate as $j$. For example, the layer $L^{1}_{j}$ consists of pipes
$P^{i}(1,j)$ for $i=1,2$ and $1\leq j\leq q$.

  * •

$C^{i}_{j}\subseteq L^{i}_{j}$ denotes the set of codewords in layer
$L^{i}_{j}$, that is, for code $C\subseteq V(K_{q}^{3})$ we have
$C^{i}_{j}=C\cap L^{i}_{j}$.

  * •

$X^{i}_{j}\subseteq L^{i}_{j}$ denotes such non-codewords $v$ in $L^{i}_{j}$
that $I(C^{i}_{j};v)=\emptyset$ and $X^{i}=\bigcup_{j=1}^{q}X^{i}_{j}$.

  * •

Let us denote $a^{i}_{j}=q-|C^{i}_{j}|$.

  * •

$M^{i}_{j}\subseteq L^{i}_{j}$ denotes the minimum dominating set of induced
subgraph $K^{3}_{q}[L^{i}_{j}]$ such that $C^{i}_{j}\subseteq M^{i}_{j}$. Note
that $K^{3}_{q}[L^{i}_{j}]\simeq K_{q}\square K_{q}$ and hence,
$|M^{i}_{j}|\geq q$.

  * •

Let us denote $f^{i}_{j}=|M^{i}_{j}|-q$. Note that
$|X^{i}_{j}|\geq(f^{i}_{j}+a^{i}_{j})^{2}$ and $f^{i}_{j}+a^{i}_{j}\geq 0$
since $f^{i}_{j}=|M^{i}_{j}|-q\geq|C^{i}_{j}|-q=-a^{i}_{j}$, ([11, page $11$
and $13$]).

###### Lemma 4.2

Let $C\subseteq V(K^{3}_{q})$ and let $K_{t}\square K_{t}$ be a subgraph of
$K^{3}_{q}[C^{i}_{j}]$ for some $i,j$. Then we have $f^{i}_{j}\geq t^{2}-t$.

###### Proof 4.3

We have $C^{i}_{j}\subseteq M^{i}_{j}$. Besides the vertices of $C^{i}_{j}$
inducing graph $K_{t}\square K_{t}$, there are $(q-t)^{2}$ vertices which are
not dominated by these vertices. Moreover, we require at least $q-t$ vertices
to dominate them. Hence, we have $|M^{i}_{j}|\geq t^{2}+(q-t)$ and thus,
$f^{i}_{j}\geq t^{2}-t$.

######  Lemma 4.4 ([11], Lemma 10)

Let $C$ be a code in $K^{3}_{q}$ and $v$ be a vertex of $K^{3}_{q}$.

  * •

If a vertex $v$ has two codewords in its $I$-set and they do not locate within
a single pipe, then there is exactly one other vertex which has those two
codewords in its $I$-set.

  * •

The $I$-set $I(v)$ is not a subset of any other $I$-set if and only if there
are at least three codewords in $I(v)$ and they do not locate within a single
pipe.

###### Theorem 4.5

We have for $q\geq 2$

$\gamma^{DLD}(K^{3}_{q})=q^{2}.$

###### Proof 4.6

We have shown in [11] that $\gamma^{SLD}(K^{3}_{q})=q^{2}$. Hence, we have
$\gamma^{DLD}(K^{3}_{q})\leq q^{2}$ by Corollary 1.5. Let us assume that $C$
is an optimal solid-locating-dominating code in $V(K^{3}_{q})$ with
$|C|<q^{2}$. Since $|C|<q^{2}$, we have a layer, say $L^{3}_{1}$, with at most
$q-1$ codewords and hence, we have $|X^{3}_{1}|\geq 1$ by Lemma 4.1. Let us
assume that $(1,1,1)\in X^{3}_{1}$. Now, we have $(i,1,1)\not\in C$ for any
$i$ and the same is true for $(1,j,1)$ for any $j$. Moreover, if we have
$(1,1,h)\not\in C$, then $I(1,1,1)\subseteq I(1,1,h)$, a contradiction.
Therefore, for each non-codeword in $X^{i}_{j}$ we have a pipe with $q-1$
codewords. Let us denote a pipe with $q-1$ codewords as $P^{i}_{C}(a,b)$ where
$i$ denotes the direction of the pipe and $(a,b)$ denotes the coordinates in
which the pipe intersects with the layer. Note that if $(a,b,z)\in X^{3}_{z}$
and $(a,b,z^{\prime})\in X^{3}_{z^{\prime}}$, then $z=z^{\prime}$.

Let us first note that we have

$|\\{P_{C}^{i}(a,b)\mid 1\leq a,b\leq q\\}|\leq q+1$ (1)

for any fixed $i\in\\{1,2,3\\}$. Otherwise, we would have
$|C|\geq(q+2)(q-1)=q^{2}+q-2>q^{2}-1$. Let us then consider the case where we
have only $q-t$, $t\geq 2$, codewords in a layer, say $L^{3}_{1}$. Then we
have $|X^{3}_{1}|\geq t^{2}$ and these vertices (or some subset of them)
induce subgraph $K_{t}\square K_{t}$ on $K^{3}_{q}$. Therefore, we have at
least $t^{2}$ copies of codeword pipes $P^{3}_{C}(a,b)$ and without loss of
generality, we may assume that values $(a,b)$ form the set $\\{(i,j)\mid 1\leq
i,j\leq t\\}$. Thus, some subset of the vertices in $C^{3}_{j}$, for any fixed
$j$ such that $2\leq j\leq q$, form an induced subgraph $K_{t}\square K_{t}$.
Therefore, we have $f^{3}_{j}\geq t^{2}-t$ for any $2\leq j\leq q$ by Lemma
4.2. Thus, we have

$|X^{3}|\geq t^{2}+\sum_{j=2}^{q}(f^{3}_{j}+a^{3}_{j})^{2}\geq
t^{2}+\sum_{j=2}^{q}f^{3}_{j}+\sum_{j=2}^{q}a^{3}_{j}\geq
t^{2}-t+(q-1)(t^{2}-t)+1=q(t^{2}-t)+1\geq 2q+1.$

Note that $\sum_{j=2}^{q}a^{3}_{j}\geq 1-t$ and if $(a,b,j)\in X^{3}_{j}$,
then $(a,b,i)\not\in X^{3}_{i}$ for each $i\neq j$. However, this is a
contradiction with (1). Therefore, we have $|C^{i}_{j}|\geq q-1$ for any
$i,j$.

Let us then consider the case where $|C^{3}_{1}|=q-1$ and $C^{3}_{1}$ induces
a discrete graph. Then for any non-codeword $v=(a,b,1)$, we have $|N(v)\cap
C^{3}_{1}|\leq 2$ and the codewords in $N(v)\cap C^{3}_{1}$ do not locate
within the same pipe. Therefore, by Lemma 4.4, we have another non-codeword
$w\in L^{3}_{1}$ such that $N(v)\cap C^{3}_{1}\subseteq N(w)$. Furthermore,
this means that there is a codeword in $P^{3}(a,b)$. Since this is true for
any non-codeword and $|L^{3}_{1}|=q^{2}$, we have $|C|\geq q^{2}$, a
contradiction.

Let us then consider the case $|C^{3}_{1}|=q-1$ for $q\geq 3$ and assume that
some codewords in $C^{3}_{1}$ are neighbours. We may assume that
$(1,1,1),(1,2,1)\in C^{3}_{1}$. Moreover, we may assume that $(q,q,1)\in
X^{3}_{1}$. Since there are at least two codewords in the pipe $P^{2}(1,1)$
and there are $q-1$ codewords in $C^{3}_{1}$, we have at least two pipes
$P^{2}(a,1)$ and $P^{2}(q,1)$ such that they contain no codewords. Therefore,
we have $(a,q,1)\in X^{1}_{1}$. Moreover, we have codeword pipes
$P_{C}^{3}(q,q)$ and $P_{C}^{3}(a,q)$. Now, we can consider layers $L^{1}_{q}$
and $L^{1}_{a}$. Let us first consider the layer $L^{1}_{q}$. First of all, it
contains the codeword pipe $P_{C}^{3}(q,q)$ and since the pipe $P^{2}(q,1)$
contains no codewords, there has to be at least one codeword in every pipe
$P^{3}(q,i)$ where $1\leq i\leq q-1$. Indeed, otherwise we would have $q-1$
codewords in some pipe $P_{C}^{1}(i,q)$, $2\leq i\leq q$, a contradiction with
pipes $P^{2}(a,1)$ and $P^{2}(q,1)$ containing no codewords. Therefore, we
have $|C^{1}_{q}|\geq 2q-2$. Furthermore, we get similarly $|C^{1}_{a}|\geq
2q-2$. However, now we have

$|C|\geq 2(2q-2)+\sum_{i=1,i\neq a}^{q-1}|C^{1}_{i}|\geq
2(2q-2)+(q-2)(q-1)=q^{2}+q-2>q^{2}-1,$

a contradiction.

##  5 Acknowledgement

The authors would like to thank María Luz Puertas Gonzalez for fruitful
discussions on the topic.

## References

  * [1] Junnila V, Laihonen T, Lehtilä T.  New results on codes for location in graphs.  In: Proceedings of Russian Finnish Symposium on Discrete Mathematics 2019\. 2019 pp. 105–116.
  * [2] Jean D, Lobstein A.  Watching systems, identifying, locating-dominating and discriminating codes in graphs: a bibliography.  _Published electronically at https://dragazo.github.io/bibdom/main.pdf_.
  * [3] Fazlollahi N, Starobinski D, Trachtenberg A.  Connected identifying codes.  _IEEE Trans. Inform. Theory_ , 2012.  58(7):4814–4824.
  * [4] Laifenfeld M, Trachtenberg A.  Disjoint identifying-codes for arbitrary graphs.  In: Proceedings International Symposium on Information Theory, 2005. ISIT 2005. IEEE, 2005 pp. 244–248.
  * [5] Ray S, Starobinski D, Trachtenberg A, Ungrangsi R.  Robust location detection with sensor networks.  _IEEE J. Sel. Areas Commun._ , 2004.  22(6):1016–1025.
  * [6] Karpovsky MG, Chakrabarty K, Levitin LB.  On a new class of codes for identifying vertices in graphs.  _IEEE Trans. Inform. Theory_ , 1998.  44(2):599–611.
  * [7] Rall DF, Slater PJ.  On location-domination numbers for certain classes of graphs.  _Congressus Numerantium_ , 1984.  45:97–106.
  * [8] Slater PJ.  Domination and location in acyclic graphs.  _Networks_ , 1987.  17(1):55–64.
  * [9] Slater PJ.  Dominating and reference sets in a graph.  _J. Math. Phys. Sci._ , 1988.  22(4):445–455.
  * [10] Junnila V, Laihonen T, Lehtilä T.  On regular and new types of codes for location-domination.  _Discrete Appl. Math._ , 2018.  247:225–241.
  * [11] Junnila V, Laihonen T, Lehtilä T.  On a Conjecture Regarding Identification in Hamming Graphs.  _Electron. J. Combin._ , 2019.  P2.
  * [12] Junnila V, Laihonen T, Lehtilä T, Puertas ML.  On Stronger Types of Locating-dominating Codes.  _Discrete Math. Theor. Comput. Sci._ , 2019.  21.
  * [13] Slater PJ.  Fault-tolerant locating-dominating sets.  _Discrete Math._ , 2002.  249(1-3):179–189.
  * [14] Rall DF, Wash K.  Identifying codes of the direct product of two cliques.  _European J. Combin._ , 2014.  36:159–171.
  * [15] Hernando C, Mora M, Pelayo IM.  Nordhaus–Gaddum bounds for locating domination.  _European J. Combin._ , 2014.  36:1–6.
  * [16] Goddard W, Wash K.  ID codes in Cartesian products of cliques.  _J. Combin. Math. Combin. Comput_ , 2013.  85:97–106.
  * [17] Haynes TW, Hedetniemi ST, Slater PJ.  Fundamentals of Domination in Graphs. 1998.  Marcel Dekker, New York, 1998.