22 2102

# Optimal local identifying and local locating-dominating codes

Pyry Herva
Department of Mathematics and Statistics
University of Turku
Turku FI-20014 Research supported by the Emil Aaltonen Foundation. Finland
<EMAIL_ADDRESS>
Tero Laihonen
Department of Mathematics and Statistics
University of Turku
Turku FI-20014 Research supported by the Academy of Finland grant 338797.
Finland
<EMAIL_ADDRESS>
Tuomo Lehtilä2
Department of Mathematics and Statistics
University of Turku
Turku FI-20014  Finland
<EMAIL_ADDRESS>
###### Abstract

We introduce two new classes of covering codes in graphs for every positive
integer $r$. These new codes are called local $r$-identifying and local
$r$-locating-dominating codes and they are derived from $r$-identifying and
$r$-locating-dominating codes, respectively. We study the sizes of optimal
local 1-identifying codes in binary hypercubes. We obtain lower and upper
bounds that are asymptotically tight. Together the bounds show that the cost
of changing covering codes into local 1-identifying codes is negligible. For
some small $n$ optimal constructions are obtained. Moreover, the upper bound
is obtained by a linear code construction. Also, we study the densities of
optimal local 1-identifying codes and local 1-locating-dominating codes in the
infinite square grid, the hexagonal grid, the triangular grid and the king
grid. We prove that seven out of eight of our constructions have optimal
densities.

###### keywords:

Local identifying codes, local locating-dominating codes, identifying codes,
locating-dominating codes, dominating sets, hypercubes, infinite grids,
discharging methods

††volume: 185††issue: 1

Local identifying and local locating-dominating codes

In honour of the 60th birthday of Iiro Honkala

##  1 Introduction and preliminaries

There are three widely studied ways to locate vertices in a graph using
subsets of vertices; namely, _resolving sets_ [1, 2] which separate vertices
using the distances to the elements in the subset, _identifying codes_ [3] and
_locating-dominating codes (or sets)_ [4, 5] both of which separate using
different neighbourhoods of the vertices in the subset. In the case of
resolving sets, the question of separating only the adjacent vertices [6, 7]
has been extensively studied, see, for example, [8] and the references
therein. Such subsets are called _local resolving sets_. Inspired by this, we
study in this paper the analogous question with respect to identifying codes
and locating-dominating codes.

Consequently, we introduce two new classes of codes derived from identifying
and locating-dominating codes and study them in some graphs. We concentrate on
the _optimal_ codes. In finite graphs by optimal we refer to the smallest
possible size of the code and in infinite graphs to the smallest possible
density of the code. Since the new code classes are closely related to
identifying and locating-dominating codes, some comparison is made. Some of
the results in this paper have been published in [9, 10].

### Graphs and codes

In this paper we consider simple, connected and undirected graphs $G=(V,E)$
with vertex set $V$ and edge set $E\subseteq\\{\\{u,v\\}\mid u,v\in V,u\neq
v\\}$. The graph $G$ is finite if its vertex set $V$ is a finite set and
infinite if $V$ is an infinite set. The (graphic) _distance_ $d(u,v)$ of two
vertices $u,v\in V$ of $G$ is the number of edges in a shortest path between
$u$ and $v$. Let $r$ be a non-negative integer. A vertex $u$ is said to _$r$
-cover_ a vertex $v$ (and vice versa) if $d(u,v)\leq r$. When $r=1$, we may
say just that $u$ _covers_ $v$. More generally, we say that a subset of the
vertex set of the graph $r$-covers a vertex $u$ if the subset has an element
which $r$-covers vertex $u$.

Any non-empty subset $C\subseteq V$ of vertices of a graph $G=(V,E)$ is called
a _code_ (in the graph $G$). The elements of $C$ are called _codewords_ and
the elements of $V\setminus C$ are called _non-codewords_. A code $C\subseteq
V$ is an _$r$ -covering code_ if it $r$-covers every vertex. If $r=1$, we may
say that $C$ is simply a _covering code_. In other words, if there is a
codeword of $C$ in distance at most $r$ from any vertex of $V$, then $C$ is an
$r$-covering code in $G$. Covering codes are also called _dominating sets_.

The _(closed) $r$-neighbourhood_ of a vertex $u\in V$ in a graph $G=(V,E)$ is
the set $N_{r}[u]=\\{v\in V\mid d(v,u)\leq r\\}$. The _open $r$-neighbourhood_
of $u$ is the set $N_{r}(u)=N_{r}[u]\setminus\\{u\\}$. The _$r$ -identifying
set_ $I_{C,r}(u)$ or the _$I$ -set_ of a vertex $u\in V$ with respect to a
code $C$ is the set

$I_{C,r}(u)=N_{r}[u]\cap C.$

For $r=1$ we denote $N[u]=N_{1}[u]$ and $I(u)=I_{C}(u)=I_{C,1}(u)$. A code
_$r$ -separates_ (or just _separates_ if $r=1$) two vertices $u$ and $v$ if
their $I$-sets are different. If $C$ separates $u$ and $v$, we may also say
that $C$ separates $u$ from $v$ (or vice versa). More generally, we say that
$C$ separates $u$ from a set of vertices $S$ if $C$ separates $u$ from every
vertex of $S$. Note that $C$ is an $r$-covering code if and only if
$I_{C,r}(u)\neq\emptyset$ for every $u\in V$.

A code in a certain class of covering codes in a finite graph is _optimal_ if
its size is the smallest among every code in the class. We also consider
optimality with respect to densities in certain infinite graphs (for the
definitions of the densities see Section 3).

Let us define two widely studied classes of covering codes for every positive
integer that are useful in locating vertices in a graph:

###### Definition 1.1

A code $C\subseteq V$ in a graph $G=(V,E)$ is an _$r$ -identifying code_ if it
is an $r$-covering code and $I_{C,r}(u)\neq I_{C,r}(v)$ for every distinct
$u,v\in V$.

###### Definition 1.2

A code $C\subseteq V$ in a graph $G=(V,E)$ is an _$r$ -locating-dominating
code_ if it is an $r$-covering code and $I_{C,r}(u)\neq I_{C,r}(v)$ for every
distinct $u,v\in V\setminus C$.

In other words, a code $C$ is an $r$-identifying code if it $r$-covers every
vertex and $r$-separates any two vertices, and it is an $r$-locating-
dominating code if it $r$-covers every vertex and $r$-separates any two non-
codewords. By identifying and locating-dominating codes we mean
$1$-identifying and $1$-locating-dominating codes, respectively.

The concept of identifying codes was introduced by Karpovsky, Chakrabarty and
Levitin in [3] and the concept of locating-dominating codes was introduced by
Slater and Rall in [4, 5]. Since their discovery, these (and many related)
classes of codes have been extensively studied in different graphs over the
years. See also the website [11] for a comprehensive list of references around
the topic.

### Our new codes: local identifying and local locating-dominating codes

Two distinct vertices of $G=(V,E)$ are called _neighbours_ or _adjacent_ if
there is an edge between them, that is, if their distance is $1$.

###### Definition 1.3

A code $C\subseteq V$ in a graph $G=(V,E)$ is a _local $r$-identifying code_
if it is an $r$-covering code and $I_{C,r}(u)\neq I_{C,r}(v)$ for any two
neighbours $u,v\in V$.

###### Definition 1.4

A code $C\subseteq V$ in a graph $G=(V,E)$ is a _local $r$-locating-dominating
code_ if it is an $r$-covering code and $I_{C,r}(u)\neq I_{C,r}(v)$ for any
two non-codeword neighbours $u,v\in V\setminus C$.

Again, by local identifying and local locating-dominating codes we mean local
$1$-identifying and local $1$-locating-dominating codes, respectively.

$u$$v$ Figure 1: A graph that admits a local 2-identifying code but does not
admit any 2-identifying codes. The darkened vertices form a local
2-identifying code.

Since any graph admits an $r$-locating-dominating code for all $r$ (it is
possible to take the whole vertex set as the code), any graph admits also a
local $r$-locating-dominating code for all $r$. However, this is not the case
for $r$-identifying and local $r$-identifying codes. Indeed, any graph that
has two distinct vertices with equal $r$-neighbourhoods admits no
$r$-identifying codes, and any graph containing two neighbours with equal
$r$-neighbourhoods admits no local $r$-identifying codes. In fact, it is
easily seen that a graph $G=(V,E)$ admits an $r$-identifying code if and only
if $N_{r}[u]\neq N_{r}[v]$ for all $u,v\in V,u\neq v$, and that $G$ admits a
local $r$-identifying code if and only if $N_{r}[u]\neq N_{r}[v]$ for all
$u,v\in V$ such that $u$ and $v$ are neighbours. For $r=1$ these conditions
are the same, that is, a graph admits an identifying code if and only if it
admits a local identifying code. For $r>1$ this is not the case. See Figure 1
for a graph that admits a local 2-identifying code but does not admit any
2-identifying codes. Indeed, the vertices $u$ and $v$ in the graph have
identical 2-neighborhoods. Hence, no code can 2-separate them. However, it is
easily verified that any two neighbors in the graph have different
2-neighborhoods. Darkened vertices denote a local $2$-identifying code in the
graph.

There is an obvious hierarchy between introduced classes of codes: they are
all covering codes, locating-dominating and local identifying codes are both
local locating-dominating codes, and identifying codes are locating-dominating
codes and also local identifying codes for any fixed covering radius and any
fixed graph. See Figure 2 for a pictorial illustration. Depending on the graph
these inclusions may or may not be strict. For example, it is quite easy to
see that in paths (finite and infinite) and in sufficiently large cycles the
classes of identifying and local identifying codes are the same [10].

From now on we concentrate on the case $r=1$. We denote by $\gamma^{ID}(G)$,
$\gamma^{LD}(G)$, $\gamma^{L-ID}(G)$ and $\gamma^{L-LD}(G)$ the cardinalities
of optimal identifying, locating-dominating, local identifying and local
locating-dominating codes, respectively, in a graph $G$. We call these values
identification, location-domination, local identification and local location-
domination numbers, respectively. In particular, we have
$\gamma^{ID}(G)\geq\gamma^{L-ID}(G)\geq\gamma^{L-LD}(G)$ and
$\gamma^{ID}(G)\geq\gamma^{LD}(G)\geq\gamma^{L-LD}(G)$ for any graph $G$
admitting an identifying code.

In [10], local $r$-identifying codes were studied in paths and in cycles. It
was proved that in both finite and infinite paths and in sufficiently large
cycles the classes of local $r$-identifying and $r$-identifying codes are
equal for all $r$.

Covering codesLocal locating-dominating codesLocating-dominating codesLocal
identifying codesIdentifying codes$\subseteq$$\subseteq$$\subseteq$ Figure 2:
Illustration of the hierarchy between different classes of covering codes.

The following lemma is useful in our forthcoming considerations. A graph $G$
is _triangle-free_ if it does not contain any triangles by which we mean that
the graph does not have any 3-cycles as induced subgraphs.

###### Lemma 1.5

A code in a triangle-free graph is a local locating-dominating code if and
only if it is a covering code.

###### Proof 1.6

First, local locating-dominating codes are covering codes by definition.

For the converse claim let $C$ be any covering code in a triangle-free graph
$G$ and assume the contrary that $C$ is not local locating-dominating. Thus,
there exist non-codeword neighbours $u$ and $v$ with equal $I$-sets. Since $C$
is a covering code, we have $I(u)=I(v)\neq\emptyset$. Hence, there is a
triangle in $G$. A contradiction.

In [12], it has been shown that finding an optimal covering code – that is, an
optimal dominating set – in a triangle-free graph (or more specifically in
chordal bipartite graphs, a subclass of triangle-free graphs) is an NP-hard
problem. Thus, the previous lemma implies the following corollary.

###### Corollary 1.7

Finding the cardinality of an optimal local locating-dominating code in a
graph $G$ is an NP-hard problem. Even when restricted to chordal bipartite
graphs.

In [13], the authors have shown that finding an optimal identifying code in a
graph $G$ is an NP-hard problem. Their proof is based on a reduction from the
well-known $3$-SAT problem. Furthermore, the exactly same reduction works also
for local identifying codes. Hence, we obtain the following corollary.

###### Corollary 1.8

Finding the cardinality of an optimal local identifying code in a graph $G$ is
an NP-hard problem.

In the following theorem, we show that it is not possible to give any useful
lower bound for local identifying (locating-dominating) codes with
identification (location-domination) number.

###### Theorem 1.9

Let $K_{2,n}$ be a complete bipartite graph on $n+2\geq 5$ vertices. We have
$\gamma^{ID}(K_{2,n})=\gamma^{LD}(K_{2,n})=n$ and
$\gamma^{L-ID}(K_{2,n})=\gamma^{L-LD}(K_{2,n})=2$.

###### Proof 1.10

Let $K_{2,n}$ have bipartitioning to sets $A$ and $B$ and let $|A|=2$. Observe
that $A$ is a local identifying code and thus, also a local locating-
dominating code. Moreover, we need at least two vertices to dominate
$K_{2,n}$. Hence, $\gamma^{L-ID}(K_{2,n})=\gamma^{L-LD}(K_{2,n})=2$.

Let us then consider usual identification and location-domination. A set
containing one vertex from $A$ and all but one from $B$ is an identifying code
(and thus, also a locating-dominating code). Moreover, to separate vertices in
$A$, we require at least one vertex from $A$ to locating-dominating code.
Furthemore, only vertices in $B$ can separate them from other vertices in $B$.
Thus, we require all but one vertex from $B$ to any locating-dominating code.
The claim follows from the fact $\gamma^{LD}(G)\leq\gamma^{ID}(G)$.

An important concept in finding lower bounds for sizes of optimal codes is the
concept of _share_ introduced by Slater in [14]. In the following we define
this concept only for $r=1$ although it can be defined for general $r$.

###### Definition 1.11

Let $C$ be a covering code in graph $G$. The share $s(c)$ of a codeword $c\in
C$ is defined as

$s(c)=\sum_{u\in N[c]}\frac{1}{|I_{C}(u)|}.$

For example, the codeword $c$ in Figure 3 has share $s(c)=1/2+1+1/3+1/3=13/6$.

$c$ Figure 3: The darkened vertices form a (non-optimal) covering code.

The following lemma is well-known and easy to prove. It provides a useful way
to find lower bounds for sizes of optimal codes.

###### Lemma 1.12

Let $C$ be a covering code in a finite graph $G=(V,E)$. If $s(c)\leq\alpha$
for every $c\in C$, then

$|C|\geq\frac{|V|}{\alpha}.$

Thus, an upper bound for the share of an arbitrary codeword provides a lower
bound for the size of the code. We have a similar lemma for shares and
densities in some infinite graphs which we will discuss in Section 3.

### Related concepts

Besides identifying and locating-dominating codes, local identifying and local
locating-dominating codes resemble also local resolving sets as we have
mentioned. Recently, a new variant of local resolving sets, nonlocal resolving
sets, was introduced in [15]. While local resolving sets distinguish adjacent
vertices, nonlocal resolving sets are their dual concept and can distinguish
any non-adjacent pair of vertices.

It is possible to define local identifying codes using list-colouring. Let
colours be some positive integers. Let $c$ be a function giving a list of
colours for each vertex in $V(G)$ for some graph $G$. We do not restrict the
maximum length of a list connected to a vertex. However, we give the following
two restrictions for the list-colouring. If $d(u,v)=2$ for $u,v\in V(G)$, then
$c(u)\cap c(v)\neq\emptyset$, that is, vertices at distance exactly two must
share a colour in their list of colours. Secondly, if $d(u,v)=1$ for $u,v\in
V(G)$, then $c(u)\cap c(v)=\emptyset$. We call this locality colouring. Since
there are $(n^{2}-n)/2$ distinct pairs of vertices in an $n$-vertex graph,
there always exists a locality colouring with $(n^{2}-n)/2$ colours.

Let us consider a dominating set $S$ in $G$ together with the following
property: For any pair of vertices $u,v\in V(G)$ with $c(u)\cap
c(v)=\emptyset$ we have $I(u)\neq I(v)$. Observe that set $S$ is a local
identifying code. Indeed, it is dominating and it separates any adjacent
vertices. Let us then consider a local identifying code $C$ in $G$. Observe
that if $c(u)\cap c(v)=\emptyset$, then $u$ and $v$ are either adjacent and
$I(u)\neq I(v)$ or $d(u,v)\geq 3$ and again $I(u)\neq I(v)$ since $C$ is
dominating. Thus, we could have defined local identifying codes also using
list-colourings. Moreover, colouring related separation/location problems have
been considered in the literature, for example, in [16, 17, 18].

In [19, 20], a concept called red-blue separation was introduced. We next show
a connection between this concept and local identification. In red-blue
separation, each vertex of graph $G$ is assigned either red or blue colour.
After that a set of vertices $S$ is a red-blue separating set if for any two
vertices $u,v\in V(G)$ we have $I(v)=I(u)$ only when $v$ and $u$ have been
assigned the same colour. Notice that domination was not required here.

Consider a bipartite graph $G$ with bipartition of vertices to sets $A$ and
$B$. Let colouring $c$ be such that we assign colour $1$ (red) to each vertex
in $A$ and colour $2$ (blue) to each vertex in $B$. Notice that any adjacent
vertices share no colours while any vertices at distance two share a colour.
Thus, this colouring is a locality colouring. Therefore, a dominating set of
graph $G$ is also a red-blue separating set together with colouring $c$ if and
only if it is a local identifying code. Hence, these concepts are closely
related. Moreover, perhaps it would be interesting to consider local
separating sets in the future, that is, local identifying codes without the
domination property.

### Structure of the paper

First in Section 2, we study local identifying codes in binary hypercubes. In
Subsection 2.1, we give some exact solutions for local identifying codes in
small hypercubes. Then, in Subsection 2.2, we give a general and
asymptotically tight lower bound for local identifying codes in hypercubes.
After that, in Subsection 2.3, we give general methods for constructing local
identifying codes in hypercubes. In particular, these constructions show that
our lower bound is essentially tight and the size of optimal local identifying
codes is significantly smaller than that of usual identifying codes in
hypercubes.

In Section 3, we consider local locating-dominating and local identifying
codes in infinite square, hexagonal (Subsection 3.1), triangular (Subsection
3.2) and king grids (Subsection 3.3). In particular, we give an optimal
construction for seven out of eight of these cases. Finally, we conclude with
Section 4.

##  2 Local identifying codes in binary hypercubes

Let us denote by $\mathbb{F}=\\{0,1\\}$ the binary field and let $n\geq 1$ be
an integer. The set of length $n$ binary words is denoted by $\mathbb{F}^{n}$
as usual. The _Hamming distance_ $d_{H}(\mathbf{x},\mathbf{y})$ of two binary
words $\mathbf{x},\mathbf{y}\in\mathbb{F}^{n}$ is the number of coordinates in
which they differ. The _binary $n$-dimensional hypercube_ is the graph
$G=(V,E)$ where $V=\mathbb{F}^{n}$ and
$E=\\{\\{\mathbf{x},\mathbf{y}\\}\mid\mathbf{x},\mathbf{y}\in\mathbb{F}^{n},d_{H}(\mathbf{x},\mathbf{y})=1\\}$,
i.e., two binary words are neighbours in the binary hypercube if and only if
their Hamming distance is 1. In fact, it is easy to see that the Hamming
distance between two binary words is the same as their graphic distance in the
binary hypercube. So, from now on by $\mathbb{F}^{n}$ we mean the above graph.

We study local identifying codes in binary hypercubes. Let us denote by
$M^{L}(n)$ the size of an optimal local identifying code and by $M(n)$ the
size of an optimal identifying code in the binary $n$-dimensional hypercube.
Moreover, we denote by $M^{LD}(n)$ and $K(n)$ the sizes of optimal locating-
dominating codes and optimal covering codes, respectively, in the binary
$n$-dimensional hypercube. Even though there has been much research concerning
identifying codes in binary hypercubes, the exact value of $M(n)$ is known
only for $2\leq n\leq 7$. In Table 1 we have listed the known values of
$M(n)$, $M^{LD}(n)$ and $K(n)$ and our contributions to the values $M^{L}(n)$
for $n\in[2,10]$. Note that the numbers $M(1)$ and $M^{L}(1)$ are not defined
since there are no identifying or local identifying codes in the binary
1-dimensional hypercube $\mathbb{F}$. Note also that since binary hypercubes
are triangle-free, the local locating-dominating codes are exactly the
covering codes in binary hypercubes by Lemma 1.5.

We start by determining the exact values of $M^{L}(n)$ for small $n$. Then we
prove a general lower bound for $M^{L}(n)$ and an upper bound by a linear code
construction. It turns out that this construction shows that our lower bound
cannot be significantly improved since for infinitely many $n$, it yields a
code whose size is very close to the lower bound (and actually to the lower
bound of covering codes). Consequently, this implies that for infinitely many
$n$ the size of an optimal local identifying code is significantly smaller
than the size of an optimal identifying code in the binary $n$-dimensional
hypercube. However, this is not the case in every graph as we will see in
Table 2 for triangular grid.

Table 1: Known values of $M(n),M^{LD}(n)$ and $K(n)$ and our contributions concerning the values of $M^{L}(n)$ for $n\in[2,10]$. Keys to the table: (A) [21], (B) [22], (C) [3], (D) [23, Appendix], (E) [24], (F) [25], (G) [26], (H) [27], (I) [28], (J) [29], (K) [30]. Left key is for the lower bound and right key for the upper bound. When lower and upper bounds are from the same source, the key is placed only on the right side. $n$ | $M(n)$ | $M^{L}(n)$ | $M^{LD}(n)$ | $K(n)$
---|---|---|---|---
2 | 3 (C) | 2 | 2 (B) | 2 (H)
3 | 4 (C) | 4 | 4 (B) | 2 (H)
4 | 7 (F) | 6 | 6 (B) | 4 (H)
5 | 10 (C) | 8 | 10 (B) | 7 (H)
6 | (G) 19 (F) | 12 – 16 | 16 – 18 (B) | (I) 12 (H)
7 | 32 (F) | 21 – 28 | 28 – 32 (B) | 16 (H)
8 | (C) 56 – 61 (A) | 35 – 48 | (B) 50 – 61 (D) | 32 (H)
9 | (C) 101 – 112 (A) | 62 – 64 | (B) 91 – 112 (A) | (K) 62 (J)
10 | (C) 183 – 208 (A) | 110 – 128 | (E) 171 – 208 (A) | 107 – 120 (K)

###  2.1 Small $n$

The following example shows that $M^{L}(2)=2$ which is strictly smaller than
$M(2)=3$.

###### Example 2.1

Let us show that $M^{L}(2)=2$. First, $M^{L}(2)\geq 2$ since any local
identifying code is a covering code and one cannot cover all the vertices of
$\mathbb{F}^{2}$ with only one codeword. However, the code $C=\\{00,11\\}$ is
a local identifying code and thus $M^{L}(2)\leq 2$.

In $\mathbb{F}^{3}$ the classes of local identifying and identifying codes are
the same:

###### Theorem 2.2

A code $C\subseteq\mathbb{F}^{3}$ is an identifying code if and only if it is
a local identifying code. Thus, $M^{L}(3)=M(3)=4$.

###### Proof 2.3

By definition, any identifying code is also a local identifying code.

For the converse direction assume on the contrary that there exists a local
identifying code $C\subseteq\mathbb{F}^{3}$ which is not an identifying code.
Notice that $C$ is a covering code. There exist
$\mathbf{x},\mathbf{y}\in\mathbb{F}^{3}$ such that
$I_{C}(\mathbf{x})=I_{C}(\mathbf{y})$. Because $C$ is a local identifying
code, $\mathbf{x}$ and $\mathbf{y}$ cannot be neighbours and hence
$d(\mathbf{x},\mathbf{y})\geq 2$. However, we cannot have
$d(\mathbf{x},\mathbf{y})=3$ since then $\mathbf{x}$ and $\mathbf{y}$ could
not cover a common codeword and hence they could not have equal non-empty
$I$-sets. Thus, $d(\mathbf{x},\mathbf{y})=2$. Without loss of generality we
may assume that $\mathbf{x}=000$ and $\mathbf{y}=110$. By the assumption that
the $I$-sets of $\mathbf{x}$ and $\mathbf{y}$ are equal, we conclude that the
symmetric difference $N[\mathbf{x}]\Delta N[\mathbf{y}]=\\{000,001,110,111\\}$
of their neighbourhoods is a subset of $\mathbb{F}^{3}\setminus C$ and hence
$C\subseteq\mathbb{F}^{3}\setminus N[\mathbf{x}]\Delta
N[\mathbf{y}]=\\{100,010,011,101\\}=C^{\prime}$. As a superset of a local
identifying code $C$, also the code $C^{\prime}$ is a local identifying code.
However, $I_{C^{\prime}}(010)=\\{010,011\\}=I_{C^{\prime}}(011)$. Since $010$
and $011$ are neighbours, this means that $C^{\prime}$ is not a local
identifying code which is a contradiction. Thus, $C$ has to be also an
identifying code.

###  2.2 A lower bound

By proving an upper bound for the share of an arbitrary codeword of an
arbitrary local identifying code, we prove the following theorem which
provides a lower bound for $M^{L}(n)$ for $n\geq 3$.

###### Theorem 2.4

For every $n\geq 3$

$M^{L}(n)\geq\frac{3\cdot 2^{n}}{3n-2}.$

###### Proof 2.5

For $n=3$ the claim follows from Theorem 2.2. So, let us assume then that
$n\geq 4$. Let $C\subseteq\mathbb{F}^{n}$ be a local identifying code and let
$\mathbf{c}\in C$ be an arbitrary codeword. We show that

$s(\mathbf{c})\leq\frac{3n-2}{3}$

which together with Lemma 1.12 gives the claim.

Since $C$ is a local identifying code, it separates $\mathbf{c}$ from its
neighbours $\mathbf{c}+\mathbf{e}_{1},\ldots,\mathbf{c}+\mathbf{e}_{n}$ where
$\mathbf{e}_{j}$ is the binary word of weight one whose $j$th component is 1.
If none of the points $\mathbf{c}+\mathbf{e}_{j}$ is a codeword, i.e., if
$I(\mathbf{c})=\\{\mathbf{c}\\}$, then each of them is covered by at least two
codewords and hence

$s(\mathbf{c})=\frac{1}{|I(\mathbf{c})|}+\sum_{j=1}^{n}\frac{1}{|I(\mathbf{c}+\mathbf{e}_{j})|}\leq
1+\frac{n}{2}.$ (1)

Let us then assume that $\mathbf{c}+\mathbf{e}_{k}\in C$ for some
$k\in\\{1,\ldots,n\\}$. In order to separate the neighbours $\mathbf{c}$ and
$\mathbf{c}+\mathbf{e}_{k}$, the code $C$ has to cover at least one of them by
an extra codeword, i.e., $|I(\mathbf{c})|\geq 3$ or
$|I(\mathbf{c}+\mathbf{e}_{k})|\geq 3$. In both cases
$|I(\mathbf{c}+\mathbf{e}_{l})|\geq 2$ for some
$l\in\\{1,\ldots,n\\}\setminus\\{k\\}$. Thus,

$s(\mathbf{c})\leq\frac{1}{3}+2\cdot\frac{1}{2}+(n-2)\cdot 1=\frac{3n-2}{3}.$

For $n\geq 4$ we have $1+\frac{n}{2}\leq\frac{3n-2}{3}$. The claim follows.

We can utilize the concept of share also in proofs when the value of $n$ is
specified as we will see in the following proof. In the proof of the following
theorem we mean by the weight of $\mathbf{x}$ the number of its coordinates
that have symbol 1.

###### Theorem 2.6

$M^{L}(4)=6.$

###### Proof 2.7

It is straight-forward to verify that the code

$C=\\{0000,0100,0010,0111,1111,1101\\}$

is a local identifying code in the binary hypercube $\mathbb{F}^{4}$. Thus,
$M^{L}(4)\leq 6$.

Let us show that $M^{L}(4)\geq 6$. Assume the contrary that $M^{L}(4)<6$. Then
there exists a local identifying code $C\subseteq\mathbb{F}^{4}$ with five
codewords. We split the proof into two cases based on whether there exists a
codeword $\mathbf{c}$ with $|I(\mathbf{c})|\geq 3$.

Case 1. Assume first that there exists a codeword $\mathbf{c}\in C$ with
$|I(\mathbf{c})|\geq 3$ and without loss of generality that
$\mathbf{c}=\mathbf{0}$ and $\\{1000,0100\\}\subseteq I(\mathbf{c})$. Consider
next the subcase with $\mathbf{1}\in C$. Let us denote the remaining codeword
with $\mathbf{c}_{5}$. The only vertex which is not covered by $C$ at this
point is $0011$. If weight of $\mathbf{c}_{5}$ is three, then
$I(\mathbf{c}_{5})=I(\mathbf{1})$. If $\mathbf{c}_{5}$ covers $0011$ and its
weight is at most two, then $I(\mathbf{1})=I(1110)$, a contradiction. Thus, we
may assume that $\mathbf{1}\not\in C$.

Since $\mathbf{1}\not\in C$, we require at least one weight three codeword
$\mathbf{c}_{4}\in C$ to cover $\mathbf{1}$. However, two codewords (other
than $\mathbf{1}$) can cover all four weight three codewords only if their
weight is two, a contradiction.

Case 2. Assume next that there does not exist a codeword $\mathbf{c}\in C$
with $|I(\mathbf{c})|\geq 3$. If
$I(\mathbf{c})=\\{\mathbf{c},\mathbf{c}^{\prime}\\}$ for some $\mathbf{c}$,
then $|I(\mathbf{c}^{\prime})|\geq 3$. Hence, we have $|I(\mathbf{c})|=1$ for
each codeword $\mathbf{c}\in C$. In this case, we consider share. As we have
counted in Equation (1), we have $s(\mathbf{c})\leq n/2+1=3$ for each
$\mathbf{c}\in C$. Thus, $|C|\geq 2^{4}/3=5\frac{1}{3}>5$. Therefore, we again
have a contradiction and $M^{L}(4)=6$.

In the following subsection we will see that there exist infinitely many $n$
for which there exists a local identifying code in $\mathbb{F}^{n}$ such that
its size is arbitrarily close to the obtained lower bound. This means that for
infinitely many $n$ the size of an optimal identifying code in the binary
$n$-dimensional hypercube is approximately at least two times larger than the
size of an optimal local identifying code.

###  2.3 Upper bounds

The _direct sum_ of two codes $C_{1}\subseteq\mathbb{F}^{n}$ and
$C_{2}\subseteq\mathbb{F}^{m}$ is the code

$C_{1}\oplus C_{2}=\\{(\mathbf{c}_{1},\mathbf{c}_{2})\mid\mathbf{c}_{1}\in
C_{1},\mathbf{c}_{2}\in C_{2}\\}\subseteq\mathbb{F}^{n+m}.$

###### Lemma 2.8

Let $C\subseteq\mathbb{F}^{n}$ be a local identifying code. Then the code
$C^{\prime}=\mathbb{F}\oplus C\subseteq\mathbb{F}^{n+1}$ is a local
identifying code if and only if $|I(\mathbf{c})|\geq 2$ for every
$\mathbf{c}\in C$.

###### Proof 2.9

Let us first assume that $C^{\prime}=\mathbb{F}\oplus C$ is a local
identifying code. Assume on the contrary that there exists a codeword
$\mathbf{c}\in C$ such that $I_{C}(\mathbf{c})=\\{\mathbf{c}\\}$. Then
$C^{\prime}$ does not separate the neighbours $(0,\mathbf{c})$ and
$(1,\mathbf{c})$. A contradiction.

For the converse direction, assume then that $|I_{C}(\mathbf{c})|\geq 2$ for
every $\mathbf{c}\in C$. Let
$\mathbf{x}^{\prime}=(a,\mathbf{x})\in\mathbb{F}^{n+1}$ where $a\in\mathbb{F}$
and $\mathbf{x}\in\mathbb{F}^{n}$. If $\mathbf{x}\in C$, then
$I_{C^{\prime}}(\mathbf{x}^{\prime})=\\{\mathbf{x}^{\prime},(a+1,\mathbf{x})\\}\cup\\{(a,\mathbf{c})\mid\mathbf{c}\in
I_{C}(\mathbf{x})\\}$ and if $\mathbf{x}\not\in C$, then
$I_{C^{\prime}}(\mathbf{x}^{\prime})=\\{(a,\mathbf{c})\mid\mathbf{c}\in
I_{C}(\mathbf{x})\\}$. Thus,
$I_{C^{\prime}}(\mathbf{x}^{\prime})\neq\emptyset$ since
$I_{C}(\mathbf{x})\neq\emptyset$ and hence $C^{\prime}$ is a covering code.
Let us then show that $C^{\prime}$ separates any two neighbours. So, let
$\mathbf{x}^{\prime}=(a,\mathbf{x})$ and $\mathbf{y}^{\prime}=(b,\mathbf{y})$
be neighbours. Assume first that $a=b$. Then $\mathbf{x}$ and $\mathbf{y}$
have to be neighbours. Since $C$ is a local identifying code, we have
$I_{C}(\mathbf{x})\neq I_{C}(\mathbf{y})$ and hence also
$I_{C^{\prime}}(\mathbf{x}^{\prime})\neq I_{C^{\prime}}(\mathbf{y}^{\prime})$.
Assume then that $a\neq b$. We have $\mathbf{x}=\mathbf{y}$ since
$\mathbf{x}^{\prime}$ and $\mathbf{y}^{\prime}$ are neighbours. By the
assumption $|I_{C}(\mathbf{c})|\geq 2$, for every $\mathbf{c}\in C$, there
exists a codeword $\mathbf{c}\in I_{C}(\mathbf{x})=I_{C}(\mathbf{y})$ such
that $\mathbf{c}\neq\mathbf{x}=\mathbf{y}$. Thus,
$(a,\mathbf{c}),(b,\mathbf{c})\in I_{C^{\prime}}(\mathbf{x}^{\prime})\triangle
I_{C^{\prime}}(\mathbf{y}^{\prime})$ and hence
$I_{C^{\prime}}(\mathbf{x}^{\prime})\neq I_{C^{\prime}}(\mathbf{y}^{\prime})$.
So, we conclude that $C^{\prime}$ separates any two neighbours and hence
$C^{\prime}$ is a local identifying code.

In the following lemma, we use the fact that if the intersection
$N[\mathbf{x}]\cap N[\mathbf{y}]\cap N[\mathbf{z}]$ of the neighbourhoods of
three distinct binary words $\mathbf{x},\mathbf{y},\mathbf{z}$ is non-empty,
then it in fact contains a unique point. This implies, in particular, that if
$|I(\mathbf{c})|\geq 3$ for some codeword $\mathbf{c}$ of a code
$C\subseteq\mathbb{F}^{n}$, then $I(\mathbf{c})$ is unique meaning that
$I(\mathbf{c}^{\prime})\neq I(\mathbf{c})$ for all $\mathbf{c}^{\prime}\in
C\setminus\\{\mathbf{c}\\}$.

###### Lemma 2.10

Let $C\subseteq\mathbb{F}^{n}$ be a code such that $|I(\mathbf{c})|\geq 3$ for
every $\mathbf{c}\in C$ and $|I(\mathbf{x})|\geq 1$ for every
$\mathbf{x}\in\mathbb{F}^{n}\setminus C$. Then $C$ is a local identifying
code.

###### Proof 2.11

By the assumptions $C$ is a covering code and thus also a local locating-
dominating code by Lemma 1.5. It remains to show that $C$ separates any two
neighbours. So, let $\mathbf{x}\in\mathbb{F}^{n}$ and
$\mathbf{y}\in\mathbb{F}^{n}$ be neighbours. If $\mathbf{c}\in C$, then
$I(\mathbf{c})$ is unique since $|I(\mathbf{c})|\geq 3$ by the assumption.
Thus, if one of $\mathbf{x}$ or $\mathbf{y}$ is a codeword of $C$, then $C$
separates them. Hence, let us assume that both $\mathbf{x}$ and $\mathbf{y}$
are non-codewords. The code $C$ separates them since it is a local locating-
dominating code.

The above lemma yields the following corollary.

###### Corollary 2.12

$M^{L}(n+2)\leq 4K(n).$

###### Proof 2.13

Let $C^{\prime}\subseteq\mathbb{F}^{n}$ be a covering code in $\mathbb{F}^{n}$
and $C=\mathbb{F}^{2}\oplus C^{\prime}$. Observe that for each $\mathbf{c}\in
C$ we have $|I(\mathbf{c})|\geq 3$. Moreover, since $C^{\prime}$ is a covering
code in $\mathbb{F}^{n}$, $C$ is a covering code in $\mathbb{F}^{n+2}$. Thus,
by Lemma 2.10, $C$ is a local identifying code.

###### Remark 2.14

An observant reader may notice that Lemma 2.10 gives also another upper bound
for $M^{L}(n+1)$. Consider a covering code $C$ such that $N(\mathbf{w})\cap
C\neq\emptyset$ for each $\mathbf{w}\in\mathbb{F}^{n}$. In this case, $C$ is
said to be a total dominating set and the minimum cardinality of a total
dominating set in $\mathbb{F}^{n}$ is denoted by $\gamma^{TD}(n)$. By Lemma
2.10, we have $M^{L}(n+1)\leq 2\gamma^{TD}(n).$ However, by [31, 32, 33], we
have $2K(n)=\gamma^{TD}(n+1)$. Hence, this approach yields the same upper
bound as Corollary 2.12.

Similar ideas as in the proof of Lemma 2.10 give also the code in the
following proposition.

###### Proposition 2.15

We have $M^{L}(6)\leq 15$.

###### Proof 2.16

Proof follows from the code
$C=\\{100000,010000,110000\\}\cup\\{001100,001110,001101\\}\cup\\{000011,$
$100011,010011\\}\cup\\{111110,111010,110110\\}\cup\\{111101,011101,101101\\}$.
First, code $C$ is covering and hence local locating-dominating. Thus, $C$
separates adjacent non-codewords. Secondly, the subgraph induced by codewords
consists of five separate paths of length three. Hence, $C$ separates all
codewords from their neighbours.

A code $C$ is a linear code if for any codewords
$\mathbf{c}_{1},\mathbf{c}_{2}\in C$, we have
$\mathbf{c}_{1}+\mathbf{c}_{2}\in C$. Next, we present a general construction
of a linear local identifying code which then gives an upper bound for
$M^{L}(n)$. Notice that if $C$ is a linear code in $\mathbb{F}^{n}$, then
$C\oplus\mathbb{F}$ is a linear code in $\mathbb{F}^{n+1}$. For a more
thorough survey on the topic see the book [27].

###### Definition 2.17

Let $s\geq 2$. A _binary Hamming code_ of length $n=2^{s}-1$ is a linear
covering code $\mathcal{H}_{s}\subseteq\mathbb{F}^{2^{s}-1}$ which contains
exactly $2^{n-s}$ codewords.

###### Theorem 2.18

For any binary Hamming code $\mathcal{H}_{s}$ the closed neighbourhoods of its
codewords partition the whole space $\mathbb{F}^{2^{s}-1}$.

Notice that by Corollary 2.12, code $\mathcal{H}_{s}\oplus\mathbb{F}^{2}$ is a
linear local identifying code in $\mathbb{F}^{n+2}$ for $n=2^{s}-1\geq 3$.
Hence, by Lemma 2.8, $\mathcal{H}_{s}\oplus\mathbb{F}^{k}$ is a linear local
identifying code in $\mathbb{F}^{n+k}$ for $k\geq 2$.

###### Corollary 2.19

Let $s,k\geq 2$ and $n=2^{s}+k-1$. Then

$M^{L}(n)\leq 2^{2^{s}+k-s-1}.$

In particular when $k=2$, we have $n=2^{s}+1$, for $s\geq 2$, and

$\frac{2^{n}}{n-2/3}\leq M^{L}(n)\leq 2^{n-\log_{2}(n-1)}=\frac{2^{n}}{n-1}.$

The lower bound is the one from Theorem 2.4. Next, we compare the lower and
upper bounds of local identifying codes to covering codes and identifying
codes. We will see that both our lower and upper bounds are quite good and
essentially tight for infinite number of values of $n$. We see that for
arbitrarily large $n=2^{s}+k-1$ where $k$ is “small” the upper bound of
Corollary 2.19 is close to the lower bound of Theorem 2.4. Actually, it is
close to the following lower bound for covering codes:
$K(n)\geq\frac{2^{n}}{n+1}$. This means that the lower bound is very close to
optimal for infinitely many $n$ and the cost (the number of extra codewords)
of turning a covering code into a local identifying code is small.

Furthermore, in [3], the authors have given the following lower bound for
identifying codes $M(n)\geq 2\cdot\frac{2^{n}}{n+1+2/n}.$ When we compare this
to the upper bound in Corollary 2.19, we notice that the cardinality of local
identifying codes is roughly half of the lower bound for identifying codes
(actually this holds even for locating-dominating codes). For example, by
Theorem 2.4 and Corollary 2.19 we are able to conclude that
$M^{L}(9)\in\\{62,63,64\\}$ while $M(9)\in\\{101,\ldots,112\\}$ and
$M^{LD}(9)\in\\{91,\ldots,112\\}$ as we can see from Table 1.

In particular, combining the above upper bound and our lower bound of Theorem
2.4, we have the following result which gives the precise value of $M^{L}(5)$.

###### Theorem 2.20

$M^{L}(5)=8.$

###### Proof 2.21

By Theorem 2.4 we have $M^{L}(5)\geq\frac{3\cdot 2^{5}}{3\cdot
5-2}=\frac{3\cdot 32}{13}\approx 7.38$ and hence $M^{L}(5)\geq 8$. On the
other hand, by Corollary 2.19 we have the upper bound

$M^{L}(5)\leq 2^{2^{2}+2-2-1}=8.$

##  3 Local identifying and local locating-dominating codes in infinite grids

Let us begin by defining the graphs we consider next. For a pictorial
illustration of these graphs see Figure 4.

###### Definition 3.1

An _infinite grid_ is one of the following four graphs.

  * •

The _square grid_ is the graph $\mathcal{S}=(\mathbb{Z}^{2},E_{\mathcal{S}})$
where

$E_{\mathcal{S}}=\\{\\{\mathbf{u},\mathbf{v}\\}\mid\mathbf{u}-\mathbf{v}\in\\{(\pm
1,0),(0,\pm 1)\\}\\}.$

  * •

The _hexagonal grid_ is the graph
$\mathcal{H}=(\mathbb{Z}^{2},E_{\mathcal{H}})$ where

$E_{\mathcal{H}}=\\{\\{\mathbf{u}=(i,j),\mathbf{v}\\}\mid\mathbf{u}-\mathbf{v}\in\\{(\pm
1,0),(0,(-1)^{i+j+1})\\}\\}.$

  * •

The _triangular grid_ is the graph
$\mathcal{T}=(\mathbb{Z}^{2},E_{\mathcal{T}})$ where

$E_{\mathcal{T}}=\\{\\{\mathbf{u},\mathbf{v}\\}\mid\mathbf{u}-\mathbf{v}\in\\{(\pm
1,0),(0,\pm 1),(1,1),(-1,-1)\\}\\}.$

  * •

The _king grid_ is the graph $\mathcal{K}=(\mathbb{Z}^{2},E_{\mathcal{K}})$
where

$E_{\mathcal{K}}=\\{\\{\mathbf{u},\mathbf{v}\\}\mid\mathbf{u}-\mathbf{v}\in\\{(\pm
1,0),(0,\pm 1),(\pm 1,\pm 1)\\}\\}.$

$(0,0)$$(a)$ The square grid $\mathcal{S}$$(0,0)$$(b)$ The hexagonal grid
$\mathcal{H}$$(0,0)$$(c)$ The triangular grid $\mathcal{T}$$(0,0)$$(d)$ The
king grid $\mathcal{K}$ Figure 4: Infinite grids.

Next, we define the concept of _density of a code_ in infinite grids.

###### Definition 3.2

Let $G$ be an infinite grid and let $C\subseteq\mathbb{Z}^{2}$ be a code in
$G$. The _density_ $D(C)$ of $C$ is defined as

$D(C)=\limsup_{n\to\infty}\frac{|C\cap Q_{n}|}{|Q_{n}|}$

where $Q_{n}=\\{(i,j)\in\mathbb{Z}^{2}\mid|i|\leq n,\ |j|\leq n\\}$.

We say that a code in some class of codes is _optimal_ if it has the smallest
density among the codes in the same class. In this section, we denote by
$\gamma^{ID}(G)$, $\gamma^{LD}(G)$, $\gamma^{L-ID}(G)$ and $\gamma^{L-LD}(G)$
the densities of optimal identifying, locating-dominating, local identifying
and local locating-dominating codes, respectively, in an infinite grid $G$.
The densities $\gamma^{ID}(G)$ and $\gamma^{LD}(G)$ are all known when $G$ is
the square, the triangular or the king grid. The number
$\gamma^{LD}(\mathcal{H})$ is also known while the number
$\gamma^{ID}(\mathcal{H})$ is currently still unknown. However, note that
interestingly the exact value of the density of optimal 2-identifying codes in
the hexagonal grid is known [34]. In Table 2 we have listed the known values
for the densities of optimal identifying and locating-dominating codes in each
infinite grid (and an interval for the density $\gamma^{ID}(\mathcal{H})$
where we know it belongs to) and our contributions to the optimal densities of
local identifying and local locating-dominating codes.

Table 2: Known values for the densities of optimal identifying and locating-dominating codes and contributions of this paper for the densities of optimal local identifying and local locating-dominating codes in infinite grids. For the densities of optimal identifying codes in the hexagonal grid and local locating-dominating codes in the triangular grid we give lower and upper bounds. $G$ | $\mathcal{S}$ | $\mathcal{H}$ | $\mathcal{T}$ | $\mathcal{K}$
---|---|---|---|---
$\gamma^{ID}(G)$ |  $\frac{7}{20}$ ([35]) |  $\frac{5}{12}$ – $\frac{3}{7}$ ([36, 37]) |  $\frac{1}{4}$ ([3]) |  $\frac{2}{9}$ ([38, 39])
$\gamma^{LD}(G)$ |  $\frac{3}{10}$ ([14]) |  $\frac{1}{3}$ ([40]) |  $\frac{13}{57}$ ([41]) |  $\frac{1}{5}$ ([40])
$\gamma^{L-ID}(G)$ | $\frac{3}{11}$ | $\frac{3}{8}$ | $\frac{1}{4}$ | $\frac{2}{9}$
$\gamma^{L-LD}(G)$ | $\frac{1}{5}$ | $\frac{1}{4}$ |  $\frac{2}{11}$ – $\frac{2}{9}$ | $\frac{3}{16}$

We study the densities of optimal local identifying and local locating-
dominating codes in these four grids. Again, we use shares and, in particular,
the following well-known lemma analogous to Lemma 1.12. For completeness, we
provide a proof for this result.

###### Lemma 3.3

Let $G$ be an infinite grid and let $C\subseteq\mathbb{Z}^{2}$ be a covering
code in $G$. If for some real $\alpha>0$ we have $s(\mathbf{c})\leq\alpha$ for
every $\mathbf{c}\in C$, then $D(C)\geq\frac{1}{\alpha}$.

###### Proof 3.4

By the assumption that $s(\mathbf{c})\leq\alpha$ for every $\mathbf{c}\in C$
and by the fact that $C$ is a covering code we have

$|Q_{n-1}|\leq\sum_{\mathbf{c}\in C\cap Q_{n}}s(\mathbf{c})\leq|C\cap
Q_{n}|\cdot\alpha$

for any $n\geq 1$. Thus,

$|C\cap Q_{n}|\geq\frac{|Q_{n-1}|}{\alpha}$

and hence

$D(C)=\limsup_{n\to\infty}\frac{|C\cap
Q_{n}|}{|Q_{n}|}\geq\limsup_{n\to\infty}\frac{|Q_{n-1}|}{\alpha\cdot|Q_{n}|}=\frac{1}{\alpha}\cdot\limsup_{n\to\infty}\frac{|Q_{n-1}|}{|Q_{n}|}=\frac{1}{\alpha}$

since $|Q_{n}|=(2n+1)^{2}$ which implies that
$\limsup_{n\to\infty}\frac{|Q_{n-1}|}{|Q_{n}|}=1$.

So, by finding an upper bound for the share of an arbitrary codeword of a
code, we obtain a lower bound for the density of the code. By analyzing the
possible shares of codewords of local identifying and local locating-
dominating codes in $G$ we get lower bounds for the numbers $\gamma^{L-ID}(G)$
and $\gamma^{L-LD}(G)$ for different grids $G$.

To improve the lower bounds obtained by analyzing the maximal shares of the
codewords of a code, we sometimes use a share shifting scheme where we modify
the share function by shifting shares among codewords according to some local
rules such that the total share remains the same. We denote by
$s^{\prime}(\mathbf{c})$ the modified share of $\mathbf{c}$ after applying a
share shifting scheme. For a code $C$ in a finite graph this means that
$\sum_{\mathbf{c}\in C}s(\mathbf{c})=\sum_{\mathbf{c}\in
C}s^{\prime}(\mathbf{c})$, and for a code $C$ in an infinite grid this means
that $\sum_{\mathbf{c}\in C\cap Q_{n}}s(\mathbf{c})\leq\sum_{\mathbf{c}\in
C\cap Q_{n+r}}s^{\prime}(\mathbf{c})$ where $r$ is the maximum distance from a
codeword to another codeword it shifts share to. The following lemma states
that an upper bound for the modified share function yields a lower bound for
the density of a code. Our share shifting scheme can be seen as a discharging
method, see [42] for more discussion on this topic.

###### Lemma 3.5

Let $G$ be an infinite grid and let $C\subseteq\mathbb{Z}^{2}$ be a covering
code in $G$. Let $s^{\prime}$ be a modified share function of $C$ obtained by
a share shifting scheme. If $s^{\prime}(\mathbf{c})\leq\alpha$ for every
$\mathbf{c}\in C$, then $D(C)\geq\frac{1}{\alpha}$.

###### Proof 3.6

Assume that in the share shifting scheme that defines $s^{\prime}$ codewords
obtain shifted share from codewords within distance $r$ from them. Since $C$
is a covering code, we have

$|Q_{n-1}|\leq\sum_{\mathbf{c}\in C\cap Q_{n}}s(\mathbf{c})$

and since the total share in $Q_{n}$ stays in $Q_{n+r}$, we have

$\sum_{\mathbf{c}\in C\cap Q_{n}}s(\mathbf{c})\leq\sum_{\mathbf{c}\in C\cap
Q_{n}}s^{\prime}(\mathbf{c})+\alpha\cdot|Q_{n+r}\setminus
Q_{n}|\leq\alpha\cdot|C\cap Q_{n}|+\alpha\cdot|Q_{n+r}\setminus Q_{n}|.$

By combining these, we get

$|C\cap Q_{n}|\geq\frac{1}{\alpha}|Q_{n-1}|-|Q_{n+r}\setminus Q_{n}|.$

Thus,

$D(C)=\limsup_{n\to\infty}\frac{|C\cap
Q_{n}|}{|Q_{n}|}\geq\frac{1}{\alpha}\limsup_{n\to\infty}\frac{|Q_{n-1}|}{|Q_{n}|}-\liminf_{n\to\infty}\frac{|Q_{n+r}\setminus
Q_{n}|}{|Q_{n}|}=\frac{1}{\alpha}-0=\frac{1}{\alpha}.$

###  3.1 The square and the hexagonal grids

Since the square and the hexagonal grids are triangle-free, Lemma 1.5 gives
the following theorem. See Figures 5(a) and 5(b) for constructions.

###### Theorem 3.7

$\gamma^{L-LD}(\mathcal{S})=\frac{1}{5}$

and

$\gamma^{L-LD}(\mathcal{H})=\frac{1}{4}.$

(a) An optimal local locating-dominating code which is also an optimal
covering code in the square grid.

(b) An optimal local locating-dominating code which is also an optimal
covering code in the hexagonal grid.

Figure 5: Local location-domination in the square and hexagonal grids.

The following two theorems give the exact values for the densities of optimal
local identifying codes in the square and the hexagonal grids. Observe that
those constructions are clearly optimal, since each vertex has exactly one
codeword in its closed neighbourhood.

###### Theorem 3.8

$\gamma^{L-ID}(\mathcal{S})=\frac{3}{11}.$

###### Proof 3.9

By a construction, in Figure 6(a), of a local identifying code in the square
grid of density $\frac{3}{11}$, we have
$\gamma^{L-ID}(\mathcal{S})\leq\frac{3}{11}$. Next, we prove that
$\gamma^{L-ID}(\mathcal{S})\geq\frac{3}{11}$ using a share shifting scheme.

Let $C$ be a local identifying code in the square grid. In our share shifting
scheme we shift $1/6$ share units from a codeword $\mathbf{c}\in C$ to its
unique codeword neighbour if $|I(\mathbf{c})|=2$. In all the other cases no
share is shifted. Let us denote by $s^{\prime}$ the modified share function
after applying the introduced scheme. We claim that
$s^{\prime}(\mathbf{c})\leq\frac{11}{3}$ for all $\mathbf{c}\in C$ which
yields by Lemma 3.5 that $D(C)\geq\frac{3}{11}$ and hence
$\gamma^{L-ID}(\mathcal{S})\geq\frac{3}{11}$. So, let $\mathbf{c}\in C$ be an
arbitrary codeword of $C$.

Assume first that $|I(\mathbf{c})|=1$, i.e., that
$I(\mathbf{c})=\\{\mathbf{c}\\}$. Every neighbour of $\mathbf{c}$ is covered
by at least 2 codewords since otherwise the code $C$ would not separate
$\mathbf{c}$ from all of its neighbours. So, in this case we have
$s(\mathbf{c})\leq 1+4\cdot\frac{1}{2}=3<\frac{11}{3}.$ Since $\mathbf{c}$ has
no codeword neighbours, no share is shifted to $\mathbf{c}$ and hence

$s^{\prime}(\mathbf{c})=s(\mathbf{c})=3<\frac{11}{3}.$

Assume then that $|I(\mathbf{c})|=2$ and let $\mathbf{c}^{\prime}$ be the
unique codeword neighbour of $\mathbf{c}$. Since $C$ separates $\mathbf{c}$
and $\mathbf{c}^{\prime}$, we have $|I(\mathbf{c}^{\prime})|\geq 3$ and hence
$s(\mathbf{c})\leq\frac{1}{2}+\frac{1}{3}+3\cdot 1=\frac{23}{6}=3\frac{5}{6}$.
Next, we shift $1/6$ share units from $\mathbf{c}$ and no share is shifted to
$\mathbf{c}$ because $\mathbf{c}$ has no codeword neighbours with exactly one
codeword neighbour. So, we have

$s^{\prime}(\mathbf{c})\leq\frac{23}{6}-\frac{1}{6}=3\frac{4}{6}=\frac{11}{3}.$

Finally, assume that $|I(\mathbf{c})|\geq 3$. If $|I(\mathbf{c})|=3$, then
$s(\mathbf{c})\leq\frac{1}{3}+2\cdot\frac{1}{2}+2\cdot
1=\frac{10}{3}=3\frac{1}{3}$ and hence
$s^{\prime}(\mathbf{c})\leq\frac{10}{3}+2\cdot\frac{1}{6}=\frac{11}{3}$. If
$|I(\mathbf{c})|\geq 4$, then
$s(\mathbf{c})\leq\frac{1}{4}+3\cdot\frac{1}{2}+1=\frac{11}{4}=2\frac{3}{4}$
and hence $s^{\prime}(\mathbf{c})\leq
2\frac{3}{4}+4\cdot\frac{1}{6}<\frac{11}{3}$.

We have shown that $s^{\prime}(\mathbf{c})\leq\frac{11}{3}$ for an arbitrary
$\mathbf{c}\in C$. The claim follows.

(a) A local identifying code of density $\frac{3}{11}$ in the square grid.

(b) A local identifying code of density $\frac{3}{8}$ in the hexagonal grid.

Figure 6: Local identifying codes in the square and hexagonal grids.

###### Theorem 3.10

$\gamma^{L-ID}(\mathcal{H})=\frac{3}{8}.$

###### Proof 3.11

By a construction in Figure 6(b) of a local identifying code in the hexagonal
grid of density $\frac{3}{8}$, we have
$\gamma^{L-ID}(\mathcal{H})\leq\frac{3}{8}$. Next, we prove that
$\gamma^{L-ID}(\mathcal{H})\geq\frac{3}{8}$ using a share shifting scheme.

Let $C$ be a local identifying code in the hexagonal grid. In our share
shifting scheme we shift $1/6$ share units from a codeword $\mathbf{c}\in C$
to its unique codeword neighbour if $|I(\mathbf{c})|=2$. In all the other
cases no share is shifted. Let us denote by $s^{\prime}$ the modified share
function after applying the introduced scheme. We claim that
$s^{\prime}(\mathbf{c})\leq\frac{8}{3}$ for all $\mathbf{c}\in C$ which yields
by Lemma 3.5 that $D(C)\geq\frac{3}{8}$ and hence
$\gamma^{L-ID}(\mathcal{H})\geq\frac{3}{8}$. So, let $\mathbf{c}\in C$ be an
arbitrary codeword of $C$.

Assume first that $|I(\mathbf{c})|=1$. Every neighbour of $\mathbf{c}$ is
covered by at least two codewords since otherwise the code $C$ would not
separate $\mathbf{c}$ from all of its neighbours. In this case we have
$s(\mathbf{c})\leq 1+3\cdot\frac{1}{2}<\frac{8}{3}$. Since $\mathbf{c}$ has no
codeword neighbours, no share is shifted to $\mathbf{c}$ and hence

$s^{\prime}(\mathbf{c})=s(\mathbf{c})<\frac{8}{3}.$

Assume then that $|I(\mathbf{c})|=2$ and let $\mathbf{c}^{\prime}$ be the
unique codeword neighbour of $\mathbf{c}$. Since $C$ separates $\mathbf{c}$
and $\mathbf{c}^{\prime}$, we have $|I(\mathbf{c}^{\prime})|\geq 3$ and hence
$s(\mathbf{c})\leq\frac{1}{2}+\frac{1}{3}+2\cdot 1=\frac{17}{6}=2\frac{5}{6}$.
Now we shift $1/6$ share units from $\mathbf{c}$ to $\mathbf{c}^{\prime}$ and
clearly no share is shifted to $\mathbf{c}$. Thus,

$s^{\prime}(\mathbf{c})\leq\frac{17}{6}-\frac{1}{6}=\frac{8}{3}.$

Finally, assume that $|I(\mathbf{c})|\geq 3$. If $|I(\mathbf{c})|=3$, then
$s(\mathbf{c})\leq\frac{1}{3}+2\cdot\frac{1}{2}+1=2\frac{1}{3}$ and hence
$s^{\prime}(\mathbf{c})\leq 2\frac{1}{3}+2\cdot\frac{1}{6}=\frac{8}{3}$. If
$|I(\mathbf{c})|=4$, then
$s(\mathbf{c})\leq\frac{1}{4}+3\cdot\frac{1}{2}=1\frac{3}{4}$ and hence
$s^{\prime}(\mathbf{c})\leq 1\frac{3}{4}+3\cdot\frac{1}{6}<\frac{8}{3}$.

###  3.2 The triangular grid

###### Theorem 3.12

$\gamma^{L-LD}(\mathcal{T})\in\left[\frac{2}{11},\frac{2}{9}\right].$

###### Proof 3.13

In Figure 7(a) we have constructed a local locating-dominating code of density
$\frac{2}{9}$. Thus, $\gamma^{L-LD}(\mathcal{T})\leq\frac{2}{9}$. Next, we
show that $\gamma^{L-LD}(\mathcal{T})\geq\frac{2}{11}$. So, let $C$ be a local
locating-dominating code in the triangular grid and let $\mathbf{c}\in C$ be
an arbitrary codeword. We show that $s(\mathbf{c})\leq\frac{11}{2}$ which
gives the claim together with Lemma 3.3.

Assume first that $\mathbf{c}$ has a codeword neighbour. We have
$s(\mathbf{c})\leq 4\cdot\frac{1}{2}+3\cdot 1=\frac{10}{2}<\frac{11}{2}$.
Assume then that $I(\mathbf{c})=\\{\mathbf{c}\\}$. Since $C$ is a local
locating-dominating code, it has to separate any two non-codeword neighbours,
and hence it can cover at most three neighbours of $\mathbf{c}$ only by
$\mathbf{c}$. Thus, $s(\mathbf{c})\leq 4\cdot
1+3\cdot\frac{1}{2}=\frac{11}{2}$.

(a) A local locating-dominating code of density $\frac{2}{9}$ in the
triangular grid.

(b) A local locating-dominating code of density $\frac{3}{16}$ in the king
grid.

Figure 7: Local identifying and locating-dominating codes in the triangular
and king grids.

###### Theorem 3.14

$\gamma^{L-ID}(\mathcal{T})=\frac{1}{4}=\gamma^{ID}(\mathcal{T}).$

###### Proof 3.15

Since any identifying code is also a local identifying code, we have the upper
bound $\gamma^{L-ID}(\mathcal{T})\leq\gamma^{ID}(\mathcal{T})=\frac{1}{4}$
(see Table 2). Next, we prove the lower bound
$\gamma^{L-ID}(\mathcal{T})\geq\frac{1}{4}$. So, let
$C\subseteq\mathbb{Z}^{2}$ be a local identifying code in the triangular grid.
We show that $D(C)\geq\frac{1}{4}$ by showing that $s(\mathbf{c})\leq 4$ for
all $\mathbf{c}\in C$ which then gives the claim by Lemma 3.3. Let
$\mathbf{c}\in C$ be an arbitrary codeword.

Assume first that $I(\mathbf{c})=\\{\mathbf{c}\\}$. Since $C$ separates
$\mathbf{c}$ from its neighbours, every neighbour of $\mathbf{c}$ is covered
by at least two codewords and hence $s(\mathbf{c})\leq 1+6\cdot\frac{1}{2}=4$.

Assume then that $|I(\mathbf{c})|\geq 2$ and let $\mathbf{c}^{\prime}\in C$ be
a codeword neighbour of $\mathbf{c}$. The codeword $\mathbf{c}$ has three
neighbours, say $\mathbf{u}_{1},\mathbf{u}_{2}$ and $\mathbf{u}_{3}$, that are
not covered by $\mathbf{c}^{\prime}$. One of them is a neighbour of the two
others. Without loss of generality we may assume that $\mathbf{u}_{2}$ is a
neighbour of both $\mathbf{u}_{1}$ and $\mathbf{u}_{3}$. It follows that
$\mathbf{u}_{1}$ and $\mathbf{u}_{3}$ are not neighbours. If $C$ covers at
least two of these three points by at least two codewords, then
$s(\mathbf{c})\leq 6\cdot\frac{1}{2}+1=4$. So, let us assume that $C$ covers
two of these points by only one codeword – with $\mathbf{c}$. Note that if $C$
covers $\mathbf{u}_{2}$ only by $\mathbf{c}$, then its neighbours
$\mathbf{u}_{1}$ and $\mathbf{u}_{3}$ are covered by at least two codewords
because $C$ – being a local identifying code – separates $\mathbf{u}_{2}$ from
its neighbours. So, we assume that
$I(\mathbf{u}_{1})=\\{\mathbf{c}\\}=I(\mathbf{u}_{3})$, and then we have
$|I(\mathbf{u}_{2})|\geq 2$ and
$I(\mathbf{c})=\\{\mathbf{c},\mathbf{c}^{\prime}\\}$. The codeword neighbour
$\mathbf{c}^{\prime}$ of $\mathbf{c}$ covers the two remaining neighbours of
$\mathbf{c}$, say $\mathbf{u}_{4}$ and $\mathbf{u}_{5}$, and of course
$\mathbf{c}$ and $\mathbf{c}^{\prime}$. Since
$I(\mathbf{c})=\\{\mathbf{c},\mathbf{c}^{\prime}\\}$, the code $C$ covers the
points $\mathbf{u}_{4},\mathbf{u}_{5}$ and $\mathbf{c}^{\prime}$ by at least
three codewords in order to separate them from their neighbour $\mathbf{c}$.
Thus, we have

$s(\mathbf{c})\leq 2\cdot\frac{1}{2}+2\cdot 1+3\cdot\frac{1}{3}=4.$

###  3.3 The king grid

Next, we consider consider the optimal densities of local locating-dominating
and local identifying codes in the king grid $\mathcal{K}$.

Let us begin with some terminology. We call the points $\mathbf{x}+(\pm 1,\pm
1)$ the _corner neighbours_ of $\mathbf{x}\in\mathbb{Z}^{2}$ and the points
$\mathbf{x}+(\pm 1,0),\mathbf{x}+(0,\pm 1)$ the _non-corner neighbours_ of
$\mathbf{x}$. If $\mathbf{y}$ is a corner neighbour of $\mathbf{x}$, then
$|N[\mathbf{y}]\cap N[\mathbf{x}]|=4$ and if $\mathbf{y}$ is a non-corner
neighbour of $\mathbf{x}$, then $|N[\mathbf{y}]\cap N[\mathbf{x}]|=6$. We say
that two corner neighbours of a point $\mathbf{x}$ are _adjoining_ if their
Euclidean distance is $2$ and they are _opposite_ if they are not adjoining,
i.e., if their Euclidean distance is $2\sqrt{2}$. Two non-corner neighbours
are adjoining if their Euclidean distance is $\sqrt{2}$ and opposite if they
are not adjoining in which case their Euclidean distance is $2$. Note that two
adjoining non-corner neighbours of a vertex are neighbours, in particular. A
non-corner neighbour of $\mathbf{x}$ is _between_ two adjoining corner
neighbours of $\mathbf{x}$ if it is at Euclidean distance 1 from both of them.

###### Theorem 3.16

$\gamma^{L-LD}(\mathcal{K})=\frac{3}{16}.$

###### Proof 3.17

By a construction we have $\gamma^{L-LD}(\mathcal{K})\leq\frac{3}{16}$, see
Figure 7(b).

Next, we show that $\gamma^{L-LD}(\mathcal{K})\geq\frac{3}{16}$. Let
$C\subseteq\mathbb{Z}^{2}$ be a local locating-dominating code in the king
grid. We claim that any $4\times 4$ square $D\subseteq\mathbb{Z}^{2}$ contains
at least three codewords of $C$. This implies that $D(C)\geq\frac{3}{16}$. Let
$\mathbf{t}\in\mathbb{Z}^{2}$ be such that
$D=\\{0,1,2,3\\}\times\\{0,1,2,3\\}+\mathbf{t}$. Let
$D^{\prime}=\\{1,2\\}\times\\{1,2\\}+\mathbf{t}$ be the $2\times 2$ square
inside of $D$ that does not intersect the border of $D$. Notice that the
neighbourhood of $D^{\prime}$ is $D$. We have four separate cases according to
the number of codewords in $D^{\prime}$.

  * •

If $|C\cap D^{\prime}|\in\\{3,4\\}$, then $|C\cap D|\geq 3$ and hence the
claim holds.

  * •

Assume that $|C\cap D^{\prime}|=2$. Let $\mathbf{a}$ and $\mathbf{b}$ be the
two non-codewords in $D^{\prime}$. They are neighbours and the two codewords
in $D^{\prime}$ are also neighbours of both $\mathbf{a}$ and $\mathbf{b}$.
This means that there must be a third codeword in $D$ which separates
$\mathbf{a}$ and $\mathbf{b}$ and hence $|C\cap D|\geq 3$.

  * •

Assume that $|C\cap D^{\prime}|=1$. We need at least two more codewords in $D$
to separate the three non-codewords in $D^{\prime}$ from each other. Thus,
$|C\cap D|\geq 3$.

  * •

Finally, assume that $|C\cap D^{\prime}|=0$. With one codeword in $D\setminus
D^{\prime}$ the code $C$ can cover at most two points of $D^{\prime}$. So, we
need at least two codewords in $D$ to cover the points of $D^{\prime}$. To
separate them we need at least three codewords in $D$. So, also in this case
$|C\cap D|\geq 3$.

Constellation
1$\mathbf{c}$$\mathbf{c}^{\prime}$$2$$1$$2$$2$$3$$2$$3$$2$$3$Constellation
2$\mathbf{c}$$\mathbf{c}^{\prime}$$2$$3$$3$$3$$1$$2$$2$$2$$2$Constellation
3$\mathbf{u}$$\mathbf{c}^{\prime}$$\mathbf{c}$$\mathbf{v}$$\frac{1}{4}$Constellation
4$\mathbf{u}$$\mathbf{c}^{\prime}$$\mathbf{c}$$\mathbf{v}$$\frac{1}{4}$ Figure
8: Constellations in the king grid. The edges have been omitted for
simplicity. Numbers adjacent to vertices denote the minimum number of
codewords that might cover them. Numbers within boxes can sometimes be
switched with each other within the same box. Constellations 3 and 4 also
illustrate shifting using Rule 1.

Finally, let us settle the question of the optimal density of local
identifying codes in the king grid. It turns out that it is $2/9$, the same as
the optimal density of identifying codes. For the proof we introduce a share
shifting scheme with the following two rules:

  * Rule 1:

If $\mathbf{c}\in C$ has $|I(\mathbf{c})|=2$ and $s(\mathbf{c})>\frac{9}{2}$,
then we shift $1/4$ share units from $\mathbf{c}$ to the adjacent corner
neighbour codeword $\mathbf{c}^{\prime}$ which has a non-corner codeword
neighbour.

  * Rule 2:

If $\mathbf{c}\in C$ has $|I(\mathbf{c})|=1$ and $s(\mathbf{c})>\frac{9}{2}$,
then we shift $1/12$ share units from $\mathbf{c}$ to two pairwise non-
adjacent codewords at (graphic) distance $2$ and Euclidean distance $\sqrt{5}$
from $\mathbf{c}$ which are covered by at least three codewords. If there are
adjacent codewords $\mathbf{c}_{1}$ and $\mathbf{c}_{2}$ which satisfy these
conditions, then we choose a codeword $\mathbf{c}_{i}$ which satisfies
$I(\mathbf{c}_{i})\not\subseteq I(\mathbf{c}_{j})$ where
$\\{i,j\\}=\\{1,2\\}$.

We have illustrated Rule $2$ in Figure 9 Constellation 5. We denote by
$s^{\prime}(\mathbf{c})$ the share of a codeword $\mathbf{c}\in C$ after
applying Rule $1$ and by $s^{\prime\prime}(\mathbf{c})$ the share of
$\mathbf{c}\in C$ after applying both Rules $1$ and $2$ (in that order). In
Lemma 3.18 and Theorem 3.20, we will notice that Rule $1$ is applied only to
codewords with $\frac{9}{2}<s(\mathbf{c})\leq\frac{19}{4}$ and Rule $2$ is
applied only to codewords with
$s(\mathbf{c})\in\\{4\frac{7}{12},4\frac{2}{3}\\}$. Moreover, after applying
them, we will have $s^{\prime\prime}(\mathbf{c})\leq\frac{9}{2}$ for every
$\mathbf{c}\in C$.

###### Lemma 3.18

Let $C$ be a local identifying code in the king grid and let
$\mathbf{c},\mathbf{c}^{\prime}\in C$ be such that $|I(\mathbf{c})|\geq 2$ and
$\mathbf{c}^{\prime}\in I(\mathbf{c})$. After applying Rule $1$, we have
$s^{\prime}(\mathbf{c})\leq 9/2$ and $s^{\prime}(\mathbf{c}^{\prime})\leq 4$
if Rule $1$ shifted share to $\mathbf{c}^{\prime}$.

###### Proof 3.19

We have two claims, that $s^{\prime}(\mathbf{c})\leq 9/2$ for all
$\mathbf{c}\in C$ and $s^{\prime}(\mathbf{c}^{\prime})\leq 4$ if Rule $1$
shifts share to $\mathbf{c}^{\prime}\in C$ (notice that Rule $1$ may shift
share to $\mathbf{c}^{\prime}$ more than once). We will confirm the second
claim each time after we have shifted share into a codeword. In the following,
we assume that $\mathbf{c}^{\prime}\in C$ is a codeword neighbour of
$\mathbf{c}\in C$.

Case 1. Assume first that $\mathbf{c}^{\prime}$ is a non-corner neighbour of
$\mathbf{c}$ and that Rule $1$ does not shift share to $\mathbf{c}$. Without
loss of generality, we may assume that $\mathbf{c}^{\prime}=\mathbf{c}+(1,0)$.
We have illustrated this case in Figure 8 Constellation 1. The codeword
$\mathbf{c}^{\prime}$ does not cover the points $\mathbf{c}+(-1,1)$,
$\mathbf{c}+(-1,0)$ and $\mathbf{c}+(-1,-1)$. At most one of these points can
be covered by exactly one codeword. Since $C$ separates $\mathbf{c}$ and
$\mathbf{c}^{\prime}$, at least one of them is covered by at least three
codewords. Also, $C$ separates the neighbours $\mathbf{c}+(0,1)$ and
$\mathbf{c}+(1,1)$ which means that at least one of them is covered by at
least three codewords. Similarly, $C$ separates the neighbours
$\mathbf{c}+(0,-1)$ and $\mathbf{c}+(1,-1)$ which means that at least one of
them is covered by at least three codewords. Thus, in this case in the
neighbourhood of $\mathbf{c}$, at most one point is covered by only one
codeword, at most five points are covered by only two codewords and at least
three points are covered by at least three codewords and hence

$s^{\prime}(\mathbf{c})=s(\mathbf{c})\leq
1+5\cdot\frac{1}{2}+3\cdot\frac{1}{3}=\frac{9}{2}.$

Case 2. Assume then that $\mathbf{c}^{\prime}$ is a corner neighbour of
$\mathbf{c}$ and that $\mathbf{c}$ does not have any non-corner codeword
neighbours. Thus, $s^{\prime}(\mathbf{c})\leq s(\mathbf{c})$. Without loss of
generality, we may assume that $\mathbf{c}^{\prime}=\mathbf{c}+(1,1)$. First,
there are at least three vertices in the closed neighbourhood of $\mathbf{c}$
covered by at least three codewords: Indeed, $\mathbf{c}^{\prime}$ covers the
points in the set
$\\{\mathbf{c},\mathbf{c}^{\prime},\mathbf{c}+(0,1),\mathbf{c}+(1,0)\\}=N[\mathbf{c}]\cap
N[\mathbf{c}^{\prime}]$ and since all of these vertices are adjacent, at most
one of them can have $\\{\mathbf{c},\mathbf{c}^{\prime}\\}$ as its $I$-set.
Hence, $\mathbf{c}^{\prime}$ has an adjacent non-corner codeword.

The codeword $\mathbf{c}^{\prime}$ does not cover the points
$\mathbf{c}+(-1,1)$, $\mathbf{c}+(-1,0)$, $\mathbf{c}+(-1,-1)$,
$\mathbf{c}+(0,-1)$ and $\mathbf{c}+(1,-1)$ among the points in
$N[\mathbf{c}]$. Clearly at most two of these points are covered by only one
codeword — $\mathbf{c}$. Let us assume that there exist two such points and
let us name them $\mathbf{u}$ and $\mathbf{v}$. Otherwise, we have the case as
in Figure 8 Constellation 2 giving $s^{\prime}(\mathbf{c})=s(\mathbf{c})\leq
1+5\cdot\frac{1}{2}+3\cdot\frac{1}{3}=\frac{9}{2}$.

Since the two non-corner neighbours of $\mathbf{c}$ that $\mathbf{c}^{\prime}$
does not cover are neighbours, at least one of $\mathbf{u}$ and $\mathbf{v}$
is a corner neighbour of $\mathbf{c}$.

Case 2.1 Assume first that $\mathbf{u}$ and $\mathbf{v}$ are both corner
neighbours of $\mathbf{c}$. If they are adjoining, then $C$ separates neither
of them from the non-corner neighbour between them. Thus, $\mathbf{u}$ and
$\mathbf{v}$ are opposite corner neighbours of $\mathbf{c}$ and hence,
$\mathbf{u}=\mathbf{c}+(-1,1)$ and $\mathbf{v}=\mathbf{c}+(1,-1)$ (or vice
versa).

Note that $\mathbf{c}^{\prime}$ is covered by at least four codewords. Indeed,
recall that at least one of $\mathbf{c}+(1,0)$ and $\mathbf{c}+(0,1)$ is
covered by at least three codewords. Moreover, since
$I(\mathbf{u})=I(\mathbf{v})=\\{\mathbf{c}\\}$, the only possible locations
for the third codeword are $\mathbf{v}^{\prime}=\mathbf{c}+(2,1)$ and
$\mathbf{u}^{\prime}=\mathbf{c}+(1,2)$. However, if only one of these two
vertices is a codeword, say $\mathbf{u}^{\prime}$, then we require a fourth
codeword in $I(\mathbf{c}^{\prime})$ to separate $\mathbf{c}^{\prime}$ and
$\mathbf{c}+(0,1)$. Thus, $|I(\mathbf{c}^{\prime})|\geq 4$. If
$\mathbf{c}+(-1,-1)\in C$, then $C$ covers it by four codewords due to the
same arguments as above and hence, $s(\mathbf{c})\leq 2\cdot
1+2\cdot\frac{1}{2}+3\cdot\frac{1}{3}+2\cdot\frac{1}{4}=\frac{9}{2}$.

So, let us assume that $\mathbf{c}+(-1,-1)\not\in C$. Thus,
$I(\mathbf{c})=\\{\mathbf{c},\mathbf{c}^{\prime}\\}$ and hence,
$\mathbf{u}^{\prime},\mathbf{v}^{\prime}\in C$. Now, $\mathbf{c}+(-2,-1)\in C$
since $C$ separates $\mathbf{c}+(-1,0)$ and $\mathbf{u}$. Similarly,
$\mathbf{c}+(-1,-2)\in C$ since $C$ separates $\mathbf{c}+(0,-1)$ and
$\mathbf{v}$. See Constellation $3$ in Figure 8. Thus,

$s(\mathbf{c})\leq 2\cdot
1+3\cdot\frac{1}{2}+3\cdot\frac{1}{3}+\frac{1}{4}=\frac{19}{4}.$

Furthermore, we can give a rough upper bound

$s(\mathbf{c}^{\prime})\leq\frac{3}{2}+\frac{5}{3}+\frac{1}{4}=3\frac{5}{12}$

as we can see from Figure 8 Constellation 3.

Now, we shift $1/4$ share units according to Rule $1$ from $\mathbf{c}$ to
$\mathbf{c}^{\prime}$. After this, we have

$s^{\prime}(\mathbf{c})\leq\frac{19}{4}-\frac{1}{4}=\frac{9}{2}$

and

$s^{\prime}(\mathbf{c}^{\prime})\leq
3\frac{5}{12}+\frac{1}{4}=3\frac{2}{3}<4.$ (2)

Indeed, observe that Rule $1$ can shift share to vertex $\mathbf{c}^{\prime}$
only once as $\mathbf{c}^{\prime}$ does not have any other suitable corner
neighbours.

Case 2.2 Finally, assume that $\mathbf{u}$ is a corner neighbour of
$\mathbf{c}$ and $\mathbf{v}$ is a non-corner neighbour of $\mathbf{c}$.
Without loss of generality, we may assume that $\mathbf{u}=\mathbf{c}+(-1,1)$
and that $\mathbf{v}=\mathbf{c}+(0,-1)$. See Constellation $4$ of Figure 8.
Now, $I(\mathbf{c})=\\{\mathbf{c},\mathbf{c}^{\prime}\\}$. We have
$\mathbf{c}+(-2,-1)\in C$ and $\mathbf{c}+(-2,-2)\in C$ because $C$ separates
$\mathbf{c}+(-1,0)$ and $\mathbf{u}$ and because $C$ separates
$\mathbf{c}+(-1,-1)$ and $\mathbf{c}+(-1,0)$, respectively. Since $C$
separates $\mathbf{c}+(0,1)$ and $\mathbf{c}$, we have $\mathbf{c}+(1,2)\in C$
and since $C$ separates $\mathbf{c}+(0,1)$ and
$\mathbf{c}^{\prime}=\mathbf{c}+(1,1)$, $\mathbf{c}^{\prime}$ is covered by at
least four codewords. The code $C$ separates $\mathbf{c}+(1,0)$ and
$\mathbf{c}$ and thus $\mathbf{c}+(1,0)$ is covered by at least three
codewords. Finally, $C$ separates $\mathbf{c}+(1,-1)$ and $\mathbf{v}$ and
hence the point $\mathbf{c}+(1,-1)$ is covered by at least two codewords.
Thus,

$s(\mathbf{c})\leq 2\cdot
1+3\cdot\frac{1}{2}+3\cdot\frac{1}{3}+\frac{1}{4}=\frac{19}{4}.$

Let us then consider $s(\mathbf{c}^{\prime})$. Recall that
$\mathbf{c}^{\prime}$ is covered by at least four codewords. Hence, at least
one of vertices
$\mathbf{c}^{\prime}+(1,-1),\mathbf{c}^{\prime}+(1,0),\mathbf{c}^{\prime}+(1,1)$
is a codeword and thus $\mathbf{c}^{\prime}+(1,0)$ is covered by at least
three codewords. Furthermore, $\mathbf{c}+(1,0)$ must be covered by at least
three codewords to separate it from $\mathbf{c}$. Moreover, at most one of
$\mathbf{c}^{\prime}+(-1,1),\mathbf{c}^{\prime}+(0,1),\mathbf{c}^{\prime}+(1,1)$
can be covered by only two codewords. Consequently, the only other neighbours
of $\mathbf{c}^{\prime}$ which can be covered by only two codewords are
$\mathbf{c}$ and $\mathbf{c}^{\prime}+(1,-1)$. Notice that since
$\mathbf{c}+(1,0)$ is covered by at least three codewords,
$\mathbf{c}^{\prime}+(1,-1)$ is covered by at least two codewords. Shares of
other points have been considered for $\mathbf{c}$ and can be re-verified with
Constellation 4 of Figure 8. Thus,

$s(\mathbf{c}^{\prime})\leq\frac{3}{2}+\frac{5}{3}+\frac{1}{4}=3\frac{5}{12}.$

When we apply Rule $1$, we shift $1/4$ share units away from $s(\mathbf{c})$
and hence $s^{\prime}(\mathbf{c})\leq\frac{9}{2}$. Moreover, we shift to
$\mathbf{c}^{\prime}$ at most $\frac{1}{2}$ share (if $\mathbf{c}+(2,0)\in C$
and it is in somewhat similar position to $\mathbf{c}$). Hence, we have

$s^{\prime}(\mathbf{c}^{\prime})\leq 3\frac{11}{12}<4.$ (3)

Together these two cases give the claim, with the observations that we have
calculated value of modified share $s^{\prime}$ for $\mathbf{c}$ and
$\mathbf{c}^{\prime}$ (see Equations (2) and (3)) whenever we have shifted
share and all cases in which share can be shifted with Rule $1$ have been
considered.

Constellation
5$\mathbf{c}$$\mathbf{c}^{\prime}$$\mathbf{c}^{\prime}$$1/12$$1/12$Constellation
6$\mathbf{v}$$\mathbf{c}^{\prime}$$\mathbf{c}$$\mathbf{u}$$\mathbf{a}$$\mathbf{b}$$\mathbf{d}$$3$$2$$3$$3$$2$$3$$2$$3$$1$Constellation
7$\mathbf{v}$$\mathbf{c}^{\prime}$$\mathbf{c}$$\mathbf{u}$$\mathbf{a}$$\mathbf{b}$$\mathbf{d}$$3$$2$$3$$3$$2$$3$$2$$3$$2$Constellation
8$\mathbf{v}$$\mathbf{c}^{\prime}$$\mathbf{c}$$\mathbf{u}$$\mathbf{a}$$\mathbf{b}$$\mathbf{d}$$3$$2$$1$$3$$2$$3$$2$$4$$2$
Figure 9: Constellations in the king grid. The edges have been omitted for
simplicity. Numbers adjacent to vertices denote the minimum number of
codewords that might cover them. Numbers within boxes can sometimes be
switched with each other within the same box.

Now, we are ready to prove the exact density of optimal local identifying
codes in the king grid.

###### Theorem 3.20

$\gamma^{L-ID}(\mathcal{K})=\frac{2}{9}.$

###### Proof 3.21

Since any identifying code is, in particular, a local identifying code, we
have $\gamma^{L-ID}(\mathcal{K})\leq\gamma^{ID}(\mathcal{K})=\frac{2}{9}$. We
prove the lower bound $\gamma^{L-ID}(\mathcal{K})\geq\frac{2}{9}$ by showing
that $s^{\prime\prime}(\mathbf{c})\leq\frac{9}{2}$ for each $\mathbf{c}\in C$.
After that, the claim follows from Lemma 3.5. Recall that we apply first Rule
$1$ and then Rule $2$ to obtain value for modified share function
$s^{\prime\prime}$. By Lemma 3.18, after applying Rule $1$, each codeword
$\mathbf{c}$ with $|I(\mathbf{c})|\geq 2$ has share of at most
$s^{\prime}(\mathbf{c})\leq\frac{9}{2}$. In the following, we consider a
codeword $\mathbf{c}$ with $I(\mathbf{c})=\\{\mathbf{c}\\}$. Thus, Rule $1$
does not shift any share into or away from $\mathbf{c}$ and
$s(\mathbf{c})=s^{\prime}(\mathbf{c})$. Moreover, also Rule $2$ cannot shift
share to $\mathbf{c}$ and hence, $s^{\prime\prime}(\mathbf{c})\leq
s(\mathbf{c})$.

Observe that now each neighbour of $\mathbf{c}$ is covered by at least two
codewords. Moreover, if three or more of them are covered by at least three
codewords, then $s^{\prime\prime}(\mathbf{c})\leq s(\mathbf{c})\leq
1+\frac{5}{2}+\frac{3}{3}=\frac{9}{2}$. Hence, we may assume that at most two
of them are covered by three or more codewords. Consider now any non-corner
neighbour $\mathbf{u}$ of $\mathbf{c}$. We may assume that
$I(\mathbf{u})=\\{\mathbf{c},\mathbf{c}^{\prime}\\}$. However,
$\mathbf{c}^{\prime}$ is also adjacent to at least one of the corner
neighbours of $\mathbf{c}$ adjacent to $\mathbf{u}$. Thus, to separate that
corner neighbour from $\mathbf{u}$, it is covered by at least three codewords.
Hence, there has to be at least two opposite corner neighbours of $\mathbf{c}$
which are covered by three codewords. Assume that $\mathbf{c}+(1,-1)$ and
$\mathbf{c}+(-1,1)$ are covered by three codewords.

Assume first that $\\{\mathbf{c}+(2,-1),\mathbf{c}+(1,-2)\\}\not\subseteq C$
and without loss of generality that $\mathbf{c}+(2,-1)\in C$. Observe that
since $\mathbf{c}+(0,-1)$ is covered by exactly two codewords, one of those
codewords is either $\mathbf{c}+(0,-2)$ or $\mathbf{c}+(-1,-2)$. However,
vertex $\mathbf{c}+(-1,-1)$ is adjacent to both of those codewords and hence,
$|I(\mathbf{c}+(-1,-1))|\geq 3$, a contradiction. Therefore,
$\\{\mathbf{c}+(2,-1),\mathbf{c}+(1,-2)\\}\subseteq C$. In this case, we have
$s(\mathbf{c})\leq 1+\frac{6}{2}+\frac{2}{3}=4\frac{2}{3}$. Here we have the
inequality since it is possible that one of the two corner neighbours is
actually covered by four codewords (in that case
$s(\mathbf{c})=4\frac{7}{12}$). Furthermore, since Rule $1$ does not affect
the codeword $\mathbf{c}$, we have $s^{\prime}(\mathbf{c})\leq 4\frac{2}{3}$.

Observe that both codewords $\mathbf{c}+(2,-1)$ and $\mathbf{c}+(1,-2)$ cannot
be covered by only two codewords since they are separated by code $C$.
Moreover, similar considerations can also be applied to codewords
$\mathbf{c}+(-2,1)$ and $\mathbf{c}+(-1,2)$. However, as they are in a
symmetric position compared to $\mathbf{c}+(2,-1)$ and $\mathbf{c}+(1,-2)$, we
do not mention them in the following arguments. Let us denote
$\mathbf{c}^{\prime}=\mathbf{c}+(2,-1)$ and assume, without loss of
generality, that $I(\mathbf{c}^{\prime})\not\subseteq I(\mathbf{c}+(1,-2))$.
Thus, at least one of vertices $\mathbf{c}+(3,0)$, $\mathbf{c}+(3,-1)$ and
$\mathbf{c}+(3,-2)$ is a codeword. Let us now divide the proof into three
cases based on which one of these three vertices is a codeword.

Case 1. $\mathbf{a}=\mathbf{c}+(3,0)\in C$: This case is illustrated in Figure
9 Constellation 6. Now, at least three of the four vertices of
$\mathbf{c}^{\prime}+\\{(0,0),$ $(1,0),$ $(1,1),$ $(0,1)\\}$ and of
$\mathbf{c}^{\prime}+\\{(0,0),(-1,0),(-1,-1),(0,-1)\\}$ are covered by at
least three codewords while the fourth is covered by at least two codewords.
Furthermore, $\mathbf{c}^{\prime}+(-1,1)$ is covered by exactly two codewords.
Thus,

$s(\mathbf{c}^{\prime})\leq 1+\frac{3}{2}+\frac{5}{3}=4\frac{1}{6}.$

Case 2. $\mathbf{b}=\mathbf{c}+(3,-1)\in C$: This case is illustrated in
Figure 9 Constellation 7. As in the previous case, at least three of the four
vertices of $\mathbf{c}^{\prime}+\\{(0,0),(1,0),(1,1),(0,1)\\}$ and of
$\mathbf{c}^{\prime}+\\{(0,0),(-1,0),(-1,-1),(0,-1)\\}$ are covered by at
least three codewords while the fourth is covered by at least two codewords.
Furthermore, $\mathbf{c}^{\prime}+(-1,1)$ and $\mathbf{c}^{\prime}+(1,-1)$ are
covered by at least two codewords. Thus,

$s(\mathbf{c}^{\prime})\leq\frac{4}{2}+\frac{5}{3}=3\frac{2}{3}.$

Case 3. $\mathbf{d}=\mathbf{c}+(3,-2)\in C$: This case is illustrated in
Figure 9 Constellation 8. Now, $\mathbf{c}^{\prime}+(-1,0)$ is covered by
three codewords, $\mathbf{c}^{\prime}+(-1,1)$ is covered by two codewords,
$\mathbf{c}^{\prime}+(-1,-1)$ by at least two codewords, both
$\mathbf{c}^{\prime}$ and $\mathbf{c}^{\prime}+(0,-1)$ are covered by at least
three codewords and one of them by at least four codewords. Furthermore, both
$\mathbf{d}$ and $\mathbf{b}$ are covered by at least two codewords and at
least one by at least three codewords. Finally, at least one of $\mathbf{a}$
and $\mathbf{c}^{\prime}+(0,1)$ is covered by at least two codewords. Thus,

$s(\mathbf{c}^{\prime})\leq
1+\frac{4}{2}+\frac{3}{3}+\frac{1}{4}=4\frac{1}{4}.$

Hence, in all three cases $s(\mathbf{c}^{\prime})\leq
4\frac{1}{4}=4\frac{3}{12}$. Moreover, if Rule $1$ shifts share to
$\mathbf{c}^{\prime}$, then $s^{\prime}(\mathbf{c}^{\prime})\leq 4$ as we have
seen in Lemma 3.18. Hence, $s^{\prime}(\mathbf{c}^{\prime})\leq 4\frac{1}{4}$.

Furthermore, there are at most three codewords at Euclidean distance
$\sqrt{5}$ from $\mathbf{c}^{\prime}$ which are covered only by themselves.
Indeed, we have $\mathbf{c}$ and other possibilities are at points
$\mathbf{c}+(4,0),\mathbf{c}+(4,-2)$ and $\mathbf{c}+(3,-3)$. However, at most
three of these vertices can be in $C$ and be covered only by themselves,
simultaneously. Hence,

$s^{\prime\prime}(\mathbf{c}^{\prime})\leq
4\frac{3}{12}+\frac{3}{12}=\frac{9}{2}.$

Therefore $s^{\prime\prime}(\mathbf{c})\leq\frac{9}{2}$ for each
$\mathbf{c}\in C$ since $4\frac{2}{3}-\frac{2}{12}=\frac{9}{2}$ and the claim
follows with Lemma 3.5.

##  4 Conclusions

We introduced two new classes of covering codes for every positive integer $r$
– the local $r$-identifying and local $r$-locating-dominating codes – and
studied them in binary hypercubes and infinite grids for $r=1$. We studied the
sizes of optimal local identifying codes in binary hypercubes and gave a
general lower bound and a general upper bound that are asymptotically close.
Also, for some small binary hypercubes precise values for the optimal codes
were found. We studied the densities of optimal local identifying and local
locating-dominating codes in (infinite) square, hexagonal, triangular and king
grids. In all except one of the cases we obtained optimal constructions.

For future research, we suggest studying the introduced new codes in binary
hypercubes and in infinite grids for $r>1$ and in different graphs. This is
especially interesting since the relationship between local 1-identification
and local $r$-identification differs from the relationship between
1-identification and $r$-identification. The same applies to location-
domination. Also, one could try improving the bounds of this paper in the
cases where the size or the density of an optimal code was not settled.

## References

  * [1] Harary F, Melter RA.  On the metric dimension of a graph.  _Ars Combin._ , 1976.  2:191–195.
  * [2] Slater PJ.  Leaves of trees.  In: Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congr. Numer., No. XIV. Utilitas Math., Winnipeg, Man., 1975 pp. 549–559.
  * [3] Karpovsky MG, Chakrabarty K, Levitin LB.  On a new class of codes for identifying vertices in graphs.  _IEEE Trans. Inf. Theory_ , 1998.  IT-44:599–611.
  * [4] Rall DF, Slater PJ.  On location-domination numbers for certain classes of graphs.  _Congr. Numer._ , 1984.  45:97–106.
  * [5] Slater PJ.  Dominating and reference sets in a graph.  _J. Math. Phys. Sci._ , 1988.  22:445–455.
  * [6] Okamoto F, Phinezy B, Zhang P.  On local metric dimensions of graphs.  _J. Combin. Math. Combin. Comput._ , 2010.  72:243–259.
  * [7] Okamoto F, Phinezy B, Zhang P.  The local metric dimension of a graph.  _Math. Bohem._ , 2010.  135(3):239–255.
  * [8] Klavẑar S, Tavakoli M.  Local metric dimension of graphs: Generalized hierarchical products and some applications.  _Appl. Math. Comput._ , 2020.  364:124676.
  * [9] Herva P, Laihonen T.  Local identifying and local locating-dominating codes in graphs.  _Proceedings of the Sixth Russian-Finnish Symposium on Discrete Mathematics_ , 2021.  URL http://urn.fi/URN:ISBN:978-952-12-4113-0.
  * [10] Herva P.  Lokaali identifiointi graafeissa (in Finnish).  Master’s thesis, University of Turku, 2020.
  * [11] Jean D, Lobstein A.  Watching systems, identifying, locating-dominating and discriminating codes in graphs.  https://dragazo.github.io/bibdom/main.pdf.
  * [12] Müller H, Brandstädt A.  The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs.  _Theor. Comput Sci._ , 1987.  53(2-3):257–265.
  * [13] Cohen GD, Honkala IS, Lobstein A, Zémor G.  On identifying codes.  In: Codes and Association Schemes. Springer, 1999 pp. 97–109.
  * [14] Slater PJ.  Fault-tolerant locating dominating sets.  _Discrete Math._ , 2002.  249:179–189.
  * [15] Klavžar S, Kuziak D.  Nonlocal metric dimension of graphs.  _Bull. Malaysian Math. Sci. Soc._ , 2023.  46(2):66.
  * [16] Chakraborty D, Foucaud F, Nandi S, Sen S, Supraja D.  New bounds and constructions for neighbor-locating colorings of graphs.  In: Algorithms and Discrete Applied Mathematics: 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023, Proceedings. Springer, 2023 pp. 121–133.
  * [17] Chartrand G, Erwin D, Henning M, Slater P, Zhang P.  The locating-chromatic number of a graph.  _Bull. Inst. Combin. Appl_ , 2002.  36(89):101.
  * [18] Esperet L, Gravier S, Montassier M, Ochem P, Parreau A.  Locally identifying coloring of graphs.  _Electron. J. Comb._ , 2012.  19(2):P40.
  * [19] Dev SR, Dey S, Foucaud F, Klasing R, Lehtilä T.  The RED-BLUE SEPARATION problem on graphs.  In: Combinatorial Algorithms: 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings. Springer, 2022 pp. 285–298.
  * [20] Dev SR, Dey S, Foucaud F, Klasing R, Lehtilä T.  The RED-BLUE SEPARATION problem on graphs.  _Theor. Comput. Sci._ , 2023.  970.
  * [21] Charon I, Cohen G, Hudry O, Lobstein A.  New identifying codes in the binary Hamming space.  _Eur. J. Comb._ , 2010.  32:491–501.
  * [22] Honkala I, Laihonen T, Ranto S.  On locating-dominating codes in binary Hamming spaces.  _Discrete Math. Theor. Comput. Sci._ , 2004.  6(2).
  * [23] Ranto S.  Identifying and locating-dominating codes in binary Hamming spaces.  Turku Centre for Computer Science, 2007.
  * [24] Junnila V, Laihonen T, Lehtilä T.  Improved lower bound for locating-dominating codes in binary Hamming spaces.  _Des. Codes Cryptogr._ , 2022.  90(1):67–85.
  * [25] Blass U, Honkala I, Litsyn S.  Bounds on identifying codes.  _Discrete Math._ , 2001.  241:119–128.
  * [26] Exoo G, Laihonen T, Ranto S.  New bounds on binary identifying codes.  _Discret. Appl. Math._ , 2008.  156(12):2250–2263.
  * [27] Cohen G, Honkala I, Litsyn S, Lobstein A.  Covering Codes.  Elsevier, 1997.
  * [28] Stanton R, Kalbfleisch J.  Covering problems for dichotomized matchings.  _Aequ. Math._ , 1968.  1:94–103.
  * [29] Wille L.  New binary covering codes obtained by simulated annealing.  _IEEE Trans. Inf. Theory_ , 1996.  42(1):300–302.
  * [30] Östergård P, Seuranen E.  Unidirectional covering codes.  _IEEE Trans. Inf. Theory_ , 2005.  52(1):336–340.
  * [31] Verstraten K.  A Generalization of the Football Pool Problem.  https://oeis.org/A238305/a238305.pdf, 2014.
  * [32] Azarija J, Henning M, Klavžar S.  (Total) Domination in Prisms.  _Electron. J. Comb._ , 2017.  24(1):P19.
  * [33] Goddard W, Henning MA.  A note on domination and total domination in prisms.  _J. Comb. Optim._ , 2018.  35:14–20.
  * [34] Junnila V, Laihonen T.  Optimal lower bound for 2-identifying codes in the hexagonal grid.  _Electron. J. Comb._ , 2012.  19(2):P38.
  * [35] Ben-Haim Y, Litsyn S.  Exact minimum density of codes identifying vertices in the square grid.  _SIAM J. Discrete Math._ , 2005.  19:69–82.
  * [36] Cukierman A, Yu G.  New bounds on the minimum density of an identifying code for the infinite hexagonal grid.  _Discret. Appl. Math._ , 2013.  161:2910–2924.
  * [37] Cohen G, Honkala I, Lobstein A.  Bounds for codes identifying vertices in the hexagonal grid.  _SIAM J. Discrete Math._ , 2000.  13:492–504.
  * [38] Charon I, Hudry O, Lobstein A.  Identifying codes with small radius in some infinite regular graphs.  _Electron. J. Comb._ , 2002.  9(1):R11.
  * [39] Cohen G, Honkala I, Lobstein A.  On codes identifying vertices in the two-dimensional square lattice with diagonals.  _IEEE Trans. on Comput._ , 2001.  50:174–176.
  * [40] Honkala I, Laihonen T.  On locating-dominating sets in infinite grids.  _Eur. J. Comb._ , 2006.  27:218–227.
  * [41] Honkala I.  An optimal locating-dominating set in the infinite triangular grid.  _Discrete Math._ , 2006.  306:2670–2681.
  * [42] Cranston DW, West DB.  An introduction to the discharging method via graph coloring.  _Discrete Mathematics_ , 2017.  340(4):766–793.