Search

The Levenshtein’s channel model for substitution errors is relevant in information retrieval where information is received through many noisy channels. In each of the channels there can occur at most $t$ errors and the decoder tries to recover the information with the aid of the channel outputs. Recently, Yaakobi and Bruck considered the problem where the decoder provides a list instead of a unique output. If the underlying code $C\subseteq \mathbb {F} _{2}^{n}$ has error-correcting capability $e$ , we write $t=e+\ell $ , ( $\ell \ge 1$ ). In this paper, we provide new (constant) bounds on the size of the list. In particular, we give using the Sauer-Shelah lemma the upper bound $\ell +1$ on the list size for large enough $n$ provided that we have a sufficient number of channels. We also show that the bound $\ell +1$ is the best possible. Most of our other new results rely on constant weight codes.

In this article, we study locating-dominating codes in binary Hamming spaces $$\mathbb {F}^n$$ . Locating-dominating codes have been widely studied since their introduction in 1980s by Slater and Rall. They are dominating sets suitable for distinguishing vertices in graphs. Dominating sets as well as locating-dominating codes have been studied in Hamming spaces in multiple articles. Previously, Honkala et al. (Discret Math Theor Comput Sci 6(2):265, 2004) have presented a lower bound for locating-dominating codes in binary Hamming spaces. In this article, we improve the lower bound for all values $$n\ge 10$$ . In particular, when $$n=11$$ , we manage to improve the previous lower bound from 309 to 317. This value is very close to the current best known upper bound of 320.

A set $R \subseteq V(G)$ is a resolving set of a graph $G$ if for all distinct vertices $v,u \in V(G)$ there exists an element $r \in R$ such that $d(r,v) \neq d(r,u)$. The metric dimension $\dim(G)$ of the graph $G$ is the minimum cardinality of a resolving set of $G$. A resolving set with cardinality $\dim(G)$ is called a metric basis of $G$. We consider vertices that are in all metric bases, and we call them basis forced vertices. We give several structural properties of sparse and dense graphs where basis forced vertices are present. In particular, we give bounds for the maximum number of edges in a graph containing basis forced vertices. Our bound is optimal whenever the number of basis forced vertices is even. Moreover, we provide a method of constructing fairly sparse graphs with basis forced vertices. We also study vertices which are in no metric basis in connection to cut-vertices and pendants. Furthermore, we show that deciding whether a vertex is in all metric bases is co-NP-hard, and deciding whether a vertex is in no metric basis is NP-hard., Comment: 22 pages, 11 figures

Resolving sets were originally designed to locate vertices of a graph one at a time. For the purpose of locating multiple vertices of the graph simultaneously, $\{\ell\}$-resolving sets were recently introduced. In this paper, we present new results regarding the $\{\ell\}$-resolving sets of a graph. In addition to proving general results, we consider $\{2\}$-resolving sets in rook's graphs and connect them to block designs. We also introduce the concept of $\ell$-solid-resolving sets, which is a natural generalisation of solid-resolving sets. We prove some general bounds and characterisations for $\ell$-solid-resolving sets and show how $\ell$-solid- and $\{\ell\}$-resolving sets are connected to each other. In the last part of the paper, we focus on the infinite graph family of flower snarks. We consider the $\ell$-solid- and $\{\ell\}$-metric dimensions of flower snarks. In two proofs regarding flower snarks, we use a new computer-aided reduction-like approach., 21 pages, 5 figures

Identifying codes and locating-dominating codes have been designed for locating irregularities in sensor networks. In both cases, we can locate only one irregularity and cannot even detect multiple ones. To overcome this issue, self-identifying codes have been introduced which can locate one irregularity and detect multiple ones. In this paper, we define two new classes of locating-dominating codes which have similar properties. These new locating-dominating codes as well as the regular ones are then more closely studied in the rook’s graphs and binary Hamming spaces. In the rook’s graphs, we present optimal codes, i.e., codes with the smallest possible cardinalities, for regular location-domination as well as for the two new classes. In the binary Hamming spaces, we present lower bounds and constructions for the new classes of codes; in some cases, the constructions are optimal. Moreover, one of the obtained lower bounds improves the bound of Honkala et al. (2004) on codes for locating multiple irregularities. Besides studying the new classes of codes, we also present record-breaking constructions for regular locating-dominating codes. In particular, we present a locating-dominating code in the binary Hamming space of length 11 with 320 vertices improving the earlier bound of 352; the best known lower bound for such code is 309 by Honkala et al. (2004).

In 2013, Goddard and Wash studied identifying codes in the Hamming graphs $K_q^n$. They stated, for instance, that $\gamma^{ID}(K_q^n)\leqslant q^{n-1}$ for any $q$ and $n\geqslant 3$. Moreover, they conjectured that $\gamma^{ID}(K_q^3)=q^2$. In this article, we show that $\gamma^{ID}(K_q^3)\leqslant q^2-q/4$ when $q$ is a power of four, which disproves the conjecture. Goddard and Wash also gave the lower bound $\gamma^{ID}(K_q^3)\geqslant q^2-q\sqrt{q}$. We improve this bound to $\gamma^{ID}(K_q^3)\geqslant q^2-\frac{3}{2} q$. Moreover, we improve the above mentioned bound $\gamma^{ID}(K_q^n)\leqslant q^{n-1}$ to $\gamma^{ID}(K_q^n)\leqslant q^{n-k}$ for $n=3\frac{q^k-1}{q-1}$ and to $\gamma^{ID}(K_q^n)\leqslant 3q^{n-k}$ for $n=\frac{q^k-1}{q-1}$, when $q$ is a prime power. For these bounds, we utilize two classes of closely related codes, namely, the self-identifying and the self-locating-dominating codes. In addition, we show that the self-locating-dominating codes satisfy the result $\gamma^{SLD}(K_q^3)=q^2$ related to the above conjecture.

Information retrieval in an associative memory was introduced in a recent paper by Yaakobi and Bruck. The associative memory is represented by a graph where the vertices correspond to the stored information units and the edges to associations between them. The goal is to find a stored information unit in the memory using input clues. In this paper, we study the minimum average number of input clues needed to find the sought information unit in the infinite king grid. We provide a geometric approach to determine the minimum number of input clues. Using this approach we are able to find optimal results and bounds on the number of input clues. The model by Yaakobi and Bruck has also applications to sensor networks monitoring and Levenshtein's sequence reconstruction problem.

A set of vertices S is a resolving set in a graph if each vertex has a unique array of distances to the vertices of S. The natural problem of finding the smallest cardinality of a resolving set in a graph has been widely studied over the years. In this paper, we wish to resolve a set of vertices (up to ź vertices) instead of just one vertex with the aid of the array of distances. The smallest cardinality of a set S resolving at most ź vertices is called ź-set-metric dimension. We study the problem of the ź-set-metric dimension in two infinite classes of graphs, namely, the two dimensional grid graphs and the n-dimensional binary hypercubes. We introduce a way to locate several intruders instead of only one of a resolving set.This prevents mistakes in the location procedure, see Example 2(i).New geometric approach compared to the usual resolving sets (Section 2).We give the complete and optimal results for the two dimensional grid graphs.Optimal results for a very high number of intruders in binary hypercubes.

Resolving sets are designed to locate an object in a network by measuring the distances to the object. However, if there are more than one object present in the network, this can lead to wrong conclusions. To overcome this problem, we introduce the concept of solid-resolving sets. In this paper, we study the structure and constructions of solid-resolving sets. In particular, we classify the forced vertices with respect to a solid-resolving set. We also give bounds on the solid-metric dimension utilizing concepts like the Dilworth number, the boundary of a graph, and locating-dominating sets. It is also shown that deciding whether there exists a solid-resolving set with a certain number of elements is an NP-complete problem.

Identifying and locating-dominating codes have been studied widely in circulant graphs of type $C_{n}(1,2,3,\dots , r)$ over the recent years. In 2013, Ghebleh and Niepel studied locating-dominating and identifying codes in the circulant graphs $C_{n}(1,d)$ for $d = 3$ and proposed as an open question the case of $d > 3$ . In this paper we study identifying, locating-dominating and self-identifying codes in the graphs $C_{n}(1,d)$ , $C_{n}(1,d-1,d)$ and $C_{n}(1,d-1,d,d + 1)$ . We give a new method to study lower bounds for these three codes in the circulant graphs using suitable grids. Moreover, we show that these bounds are attained for infinitely many parameters n and d. In addition, new approaches are provided which give the exact values for the optimal self-identifying codes in $C_{n}(1,3)$ and $C_{n}(1,4)$ .

Information retrieval in associative memories was studied in a recent paper by Yaakobi and Bruck (2012). Associations between memory entries give us the $t$ -neighbourhood of an entry. In their model, an information unit is retrieved from the memory with the aid of input clues, which are chosen from a reference set. In this paper, we consider the situation where the information unit is found unambiguously using the associated $t$ -neighbourhoods of the input clues. A varying number of input clues are allowed, but a limit $m_{u}$ on the maximum number of them is imposed. Of course, we would like $m_{u}$ to be as small as possible. We consider the problem over the binary Hamming space $ \mathbb {F}^{n}$ and focus on the minimum of $m_{u}$ , denoted by $\nu (n;t)$ . Using linear reference sets, we show that $\nu (n;2) \leq 5$ for any $n \geq 9$ . We also give infinite families of reference sets, which provide good bounds on $\nu (n;t)$ for $t=3$ . In addition, efficient methods are given to obtain bounds on $\nu (n;t)$ for any $t$ from known reference sets. We also discuss the applications of this model to the Levenshtein’s sequence reconstruction problem and the sensor network monitoring.

The main problem in information storage has previously been how large amounts of data can be stored. However, the technological development over the years has been able to give rather satisfactory answers to this problem. Recently, the focus has shifted towards determining how stored information can be efficiently retrieved. This problem is addressed in an article by E. Yaakobi and J. Bruck (2012), where information retrieval in associative memories is studied. In this paper, we focus on the case where the retrieved information unit is unambiguous. In particular, we present characterizations and study various extremal properties of such associative memories. Moreover, the algorithmic complexity of certain naturally rising problems is considered.

In this paper, we introduce t-revealing codes in the binary Hamming space Fn. Let C ⊆ Fn be a code and denote by I t {C; x) the set of codewords of C which are within (Hamming) distance t from a word x ∊ Fn. A code C is t-revealing if the majority voting on the coordinates of the words in I t (C; x) gives unambiguously x. These codes have applications, for instance, to the list decoding problem of the Levenshtein's channel model, where the decoder provides a list based on several different outputs of the channel with the same input, and to the information retrieval problem of the Yaakobi-Bruck model of associative memories. We give t-revealing codes which improve some of the key parameters for these applications compared to earlier code constructions, namely, the length of the output list L of the decoder and the maximal number of input clues m needed for information retrieval.

Location detection in sensor networks can be handled with so called identifying codes. For an identifying code to work properly, it is required that no sensors are malfunctioning. Previously, malfunctioning sensors have been typically coped with robust identifying codes. However, they are rather large and, hence, imply high signal interference and energy consumption. To overcome these issues, collections of disjoint identifying codes have been proposed for coping with malfunctioning sensors. However, these collections have some problems regarding detection of malfunctioning sensors and, moreover, it seems unnecessary to restrict oneself to disjoint codes. In this paper, we discuss a certain type of identifying codes, for which the detection of malfunctioning sensors is easy, and based on these codes we design a collection of codes tolerant against malfunctions. We present some results on general graphs as well as optimal constructions in rook's graphs and binary Hamming spaces.

In a recent paper by Yaakobi and Bruck, the problem of information retrieval in associative memories has been considered. In an associative memory, each memory entry is associated to the neighboring entries. When searching information, a fixed number of input clues are given and the output set is formed by the entries associated to all the input clues. The maximum size of an output set is called the uncertainty of the associative memory. In this paper, we study the problem of information retrieval in associative memories with small uncertainty. In particular, we concentrate on the cases where the memory entries and their associations form a binary Hamming space or an infinite square grid. Particularly, we focus on minimizing the number of input clues needed to retrieve information with small uncertainty and present good constructions some of which are optimal, i.e., use the smallest possible number of clues.

In this paper, we introduce t-revealing codes in the binary Hamming space F n . Let C ⊆ F n be a code and denote by I t ( C ; x ) the set of elements of C which are within (Hamming) distance t from a word x ∈ F n . A code C is t-revealing if the majority voting on the coordinates of the words in I t ( C ; x ) gives unambiguously x. These codes have applications, for instance, to the list decoding problem of the Levenshtein's channel model, where the decoder provides a list based on several different outputs of the channel with the same input, and to the information retrieval problem of the Yaakobi-Bruck model of associative memories. We give t-revealing codes which improve some of the key parameters for these applications compared to earlier code constructions.

The problem of identifying a single arbitrary edge in a graph using edge-identifying codes was recently considered by Foucaud et al. (in press) [4] . In this paper, we focus on locating more than one edge. First, we classify the graphs in which this is possible. Furthermore, for such graphs, we give a simple characterization of edge-identifying codes. Using the characterization, we give various lower and upper bounds for edge-identifying codes in terms of the order and size of a graph. In particular, codes with the minimum cardinality are obtained with the aid of 2-factors. In addition, we consider how the cardinality of the smallest edge-identifying codes behaves when an edge is added to a graph.

Bertrand, Charon, Hudry and Lobstein studied, in their paper in 2004 [1], r-locating-dominating codes in paths P"n. They conjectured that if r>=2 is a fixed integer, then the smallest cardinality of an r-locating-dominating code in P"n, denoted by M"r^L^D(P"n), satisfies M"r^L^D(P"n)[email protected]?(n+1)/[email protected]? for infinitely many values of n. We prove that this conjecture holds. In fact, we show a stronger result saying that for any r>=3 we have M"r^L^D(P"n)[email protected]?(n+1)/[email protected]? for all n>=n"r when n"r is large enough. In addition, we solve a conjecture on location-domination with segments of even length in the infinite path.

The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin. These codes find their application, for example, in sensor networks. The network is modelled by a graph. In this paper, the goal is to find good identifying codes in a natural setting, that is, in a graph E"r=(V,E) where V=Z^2 is the set of vertices and each vertex (sensor) can check its neighbours within Euclidean distance r. We also consider a graph closely connected to a well-studied king grid, which provides optimal identifying codes for E"5 and E"1"3.

We consider identifying codes in binary Hamming spaces F^n, i.e., in binary hypercubes. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks. Let C be a subset of F^n. For any subset X of F^n, denote by I_r(X)=I_r(C;X) the set of elements of C within distance r from at least one x in X. Now C is called an (r, 13 pages

A nonempty set of words in a binary Hamming space Fn is called an r-identifying code if for every word the set of codewords within distance r from it is unique and nonempty. The smallest possible cardinality of an r-identifying code is denoted by Mr(n). In this paper, we consider questions closely related to the open problem whether Mt+r(n+m)⩽Mt(m)Mr(n) is true. For example, we show results like M1+r(n+m)⩽4M1(m)Mr(n), which improve previously known bounds. We also consider codes which identify sets of words of size at most ℓ. The smallest cardinality of such a code is denoted by Mr(⩽ℓ)(n). We prove that Mr+t(⩽ℓ)(n+m)⩽Mr(⩽ℓ)(n)Mt(⩽ℓ)(m) is true for all ℓ⩾r+3 when r⩾1 and t=1. We also obtain a result M1(n+1)⩽(2+εn)M1(n) where εn→0 when n→∞. This bound is related to the conjecture M1(n+1)⩽2M1(n). Moreover, we give constructions for the best known 1-identifying codes of certain lengths.

The problem of graphs admitting identifying codes is a recent topic. In this paper, we solve a question concerning the existence of ℓ-regular graphs admitting (1,≤ℓ)-identifying code. Moreover, our girth approach gives some improvements on the number of vertices of graphs which admit identifying codes.

In binary Hamming spaces, we construct new 1-identifying codes from 2-fold 1-coverings that are 1-identifying. We improve on previously known upper bounds for the cardinalities of 1 -identifying codes of many lengths when n > 10. We construct t-identifying codes using the direct sum of t 1-identifying codes. This solves partly an open problem posed by Blass, Honkala, and Litsyn in 2001. We also prove a general result concerning the direct sum of a t-identifying code with the whole space of any dimension.

Assume that G=(V, E) is an undirected graph, and [email protected]?V. For every [email protected]?V, denote I"r(G; v)={[email protected]?C: d(u,v)@?r}, where d(u,v) denotes the number of edges on any shortest path from u to v in G. If all the sets I"r(G; v) for [email protected]?V are pairwise different, and none of them is the empty set, the code C is called r-identifying. The motivation for identifying codes comes, for instance, from finding faulty processors in multiprocessor systems or from location detection in emergency sensor networks. The underlying architecture is modelled by a graph. We study various types of identifying codes that are robust against six natural changes in the graph; known or unknown edge deletions, additions or both. Our focus is on the radius r=1. We show that in the infinite square grid the optimal density of a 1-identifying code that is robust against one unknown edge deletion is 1/2 and the optimal density of a 1-identifying code that is robust against one unknown edge addition equals 3/4 in the infinite hexagonal mesh. Moreover, although it is shown that all six problems are in general different, we prove that in the binary hypercube there are cases where five of the six problems coincide.

Fault diagnosis of multiprocessor systems gives the motivation for robust identifying codes. We provide robust identifying codes for the square and king grids. Often we are able to find optimal such codes.

Determining a malfunctioning component in a processor network gives the motivation for locating–dominating sets. It is shown that the smallest possible density of a locating–dominating set in the king grid equals 1/5 and in the hexagonal mesh 1/3. Moreover, we discuss a natural modification of locating–dominating sets.

A subset C of vertices in a connected graph G=(V,E) is called (r,⩽l)-identifying if for all subsets L⊆V of size at most l, the sets I(L), consisting of all the codewords which are within graphic distance r from at least one element in L, are different. It is proved that the minimum possible density of a (1,⩽2)-identifying code in the triangular grid is 9/16.

A motivation for identifying codes comes from quality control in multiprocessor systems, that is, we are able, with the aid of these codes, to find faulty processors in such a system. We give a construction of two infinite families of optimal codes, which identify up to two malfunctioning processors in Hamming spaces.

Fault diagnosis of multiprocessor systems gives the motivation for identifying codes. In this paper we provide an infinite sequence of optimal strongly (1, ≤l)-identifying codes in Hamming spaces for every l when l≥ 3.

Let $G=(V,E)$ be an undirected graph without loops and multiple edges. A subset $C\subseteq V$ is called \emph{identifying} if for every vertex $x\in V$ the intersection of $C$ and the closed neighbourhood of $x$ is nonempty, and these intersections are different for different vertices $x$. Let $k$ be a positive integer. We will consider graphs where \emph{every} $k$-subset is identifying. We prove that for every $k>1$ the maximal order of such a graph is at most $2k-2.$ Constructions attaining the maximal order are given for infinitely many values of $k.$ The corresponding problem of $k$-subsets identifying any at most $\ell$ vertices is considered as well., 21 pages

We call a subset $C$ of vertices of a graph $G$ a $(1,\leq l)$-identifying code if for all subsets $X$ of vertices with size at most $\ell$, the sets $\{c\in C~|~\exists u\in X, d(u,c)\leq 1\}$ are distinct. The concept of identifying codes was introduced in 1998 by Karpovsky, Chakrabarty and Levitin. Identifying codes have been studied in various grids. In particular, it has been shown that there exists a $(1,\leq 2)$-identifying code in the king grid with density $\frac{3}{7}$ and that there are no such identifying codes with density smaller than $\frac{5}{12}$. Using a suitable frame and a discharging procedure, we improve the lower bound by showing that any $(1,\leq 2)$-identifying code of the king grid has density at least $\frac{47}{111}$. This reduces the gap between the best known lower and upper bounds on this problem by more than $56\%$.

A binary code C of lengt n is called (t,>=2)-identifying if for all the words z and not equal words x and y in a Hamming space the sets (Bt>/sub sub /sub sub /sub

We consider upper bounds on two fundamental parameters of a code; minimum distance and covering radius. New upper bounds on the covering radius of non-binary linear codes are derived by generalizing a method due to S. Litsyn and A. Tietavainen lt:newu and combining it with a new upper bound on the asymptotic information rate of non-binary codes. The upper bound on the information rate is an application of a shortening method of a code and is an analogue of the Shannon-Gallager-Berlekamp straight line bound on error probability. These results improve on the best presently known asymptotic upper bounds on minimum distance and covering radius of non-binary codes in certain intervals.

Locating faulty processors in a multiprocessor system gives the motivation for identifying codes. Denote by l the maximum number of simultaneously malfunctioning processors. We show that if l/spl ges/3, then the problem of finding the smallest cardinality of a (1, /spl les/l)-identifying code in a binary hypercube is equivalent to the problem of finding the smallest size of a (2l-1)-fold 1-covering. This observation yields infinite sequences of optimal identifying codes for every l (l/spl ges/3).

International audience; The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. The identifying codes can be applied, for example, to sensor networks. In this paper, we consider as sensors the set Z^2 where one sensor can check its neighbours within Euclidean distance r. We construct tolerant identifying codes in this network that are robust against some changes in the neighbourhood monitored by each sensor. We give bounds for the smallest density of a tolerant identifying code for general values of r and Delta. We also provide infinite families of values (r,Delta) with optimal such codes and study the case of small values of r.

International audience

We show that for a code used for error detection in the binary-symmetric channel (BSC), the probability of an undetected error can have several local maxima. In particular, we construct a code with three local maxima in (0, 1/2), a code with five local maxima in (0, 1); and a linear code with two local maxima in (0, 1/2) and a linear code with three local maxima in (0, 1).

In this paper a characterization of the general relation between linear multisecret-sharing schemes and error-correcting codes is presented. A bridge between linear multisecret-sharing threshold schemes and maximum distance separable codes is set up. The information hierarchy of linear multisecret-sharing schemes is also established. By making use of the bridge several linear multisecret-sharing threshold schemes based on Reed-Solomon codes, generalized Reed-Solomon codes, Bossen-Yau redundant residue codes are described, which can detect and correct cheatings. The relations between linear multisecret-sharing threshold schemes and some threshold schemes for single-secret sharing are pointed out.

Identifying codes are designed for locating faulty processors in multiprocessor systems. In this paper we consider a natural extension of this problem and introduce strongly identifying codes. Several lower bounds and constructions are given and relations between different types of identifying codes are examined.

Codes for strong identification are considered. The motivation for these codes comes from locating faulty processors in a multiprocessor system. Constructions and lower bounds on these codes are given. In particular, we provide two infinite families of optimal strongly identifying codes, which can locate up to two malfunctioning processors in a binary hypercube.

The original motivation for identifying codes comes from fault diagnosis in multiprocessor systems. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks. In this paper, we concentrate on identification in binary Hamming spaces. We give a new lower bound on the cardinality of r-identifying codes when r>=2. Moreover, by a computational method, we show that M"1(6)=19. It is also shown, using a non-constructive approach, that there exist asymptotically good (r,@?@?)-identifying codes for fixed @?>=2. In order to construct (r,@?@?)-identifying codes, we prove that a direct sum of r codes that are (1,@?@?)-identifying is an (r,@?@?)-identifying code for @?>=2.

Let @?, n and r be positive integers. Define F^n={0,1}^n. The Hamming distance between words x and y of F^n is denoted by d(x,y). The ball of radius r is defined as B"r(X)={y@?F^n|@?x@?X:d(x,y)@?r}, where X is a subset of F^n. A code C@?F^n is called (r,@?@?)-identifying if for all X,Y@?F^n such that |X|@?@?, |Y|@?@? and X Y, the sets B"r(X)@?C and B"r(Y)@?C are different. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. In this paper, we present various results concerning (r,@?@?)-identifying codes in the Hamming space F^n. First we concentrate on improving the lower bounds on (r,@?1)-identifying codes for r>1. Then we proceed by introducing new lower bounds on (r,@?@?)-identifying codes with @?>=2. We also prove that (r,@?@?)-identifying codes can be constructed from known ones using a suitable direct sum when @?>=2. Constructions for (r,@?2)-identifying codes with the best known cardinalities are also given.

Locating-dominating codes in a graph find their application in sensor networks and have been studied extensively over the years. A locating-dominating code can locate one object in a sensor network, but if there is more than one object, it may lead to false conclusions. In this paper, we consider stronger types of locating-dominating codes which can locate one object and detect if there are multiple objects. We study the properties of these codes and provide bounds on the smallest possible size of these codes, for example, with the aid of the Dilworth number and Sperner families. Moreover, these codes are studied in trees and Cartesian products of graphs. We also give the complete realization theorems for the coexistence of the smallest possible size of these codes and the optimal locating-dominating codes in a graph.

An $r$-identifying code in a graph $G = (V,E)$ is a subset $C \subseteq V$ such that for each $u \in V$ the intersection of $C$ and the ball of radius $r$ centered at $u$ is non-empty and unique. Previously, $r$-identifying codes have been studied in various grids. In particular, it has been shown that there exists a $2$-identifying code in the hexagonal grid with density $4/19$ and that there are no $2$-identifying codes with density smaller than $2/11$. Recently, the lower bound has been improved to $1/5$ by Martin and Stanton (2010). In this paper, we prove that the $2$-identifying code with density $4/19$ is optimal, i.e. that there does not exist a $2$-identifying code in the hexagonal grid with smaller density.

Identifying codes are designed for locating faulty processors in multiprocessor systems. In this paper we consider a natural extension of this problem and introduce strongly identifying codes. Lower bounds and constructions are given and relations between different types of identifying codes are examined.

Locating faulty processors in a multiprocessor system gives the motivation for locating-dominating codes. We consider these codes in binary hypercubes and generalize the concept for the situation in which we want to locate more than one malfunctioning processor.