An edge metric basis of a connected graph G is a smallest possible set of vertices S of G satisfying the following: for any two edges e , f of G there is a vertex s ∈ S such that the distances from s to e and f differ. The cardinality of an edge metric basis is the edge metric dimension of G . In this article we consider the existence of vertices in a graph G such that they must belong to each edge metric basis of G , and we call them edge basis forced vertices . On the other hand, we name edge void vertices those vertices which do not belong to any edge metric basis. Among other results, we first deal with the computational complexity of deciding whether a given vertex is an edge basis forced vertex or an edge void vertex. We also establish some tight bounds on the number of edge basis forced vertices of a graph, as well as, on the number of edges in a graph having at least one edge basis forced vertex. Moreover, we show some realization results concerning which values for the integers n , k and f allow to confirm the existence of a graph G with n vertices, f edge basis forced vertices and edge metric dimension k .

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

Levenshtein’s sequence reconstruction model plays an essential role in information retrieval in DNA-based storage systems. In this model, a word ${\text{x}} \in {\mathbb{Z}}_q^n$ is transmitted through N noisy channels, and the goal is to recover the original word exactly, or with a small uncertainty ${\mathcal{L}}$, using the outputs from these channels. Errors occurring in the channels usually involve substitutions, insertions or deletions. In this paper, we focus on insertion errors, which we represent using (so-called) insertion vectors. One of the main questions in this context is determining the minimum number of channels N required to recover the word either unambiguously or within a given precision ${\mathcal{L}}$. The original formulation of Levenshtein’s reconstruction problem requires that all the outputs from the channels are distinct. However, different channels may produce the same output word even when different errors occur. In this paper, we investigate two generalized reconstruction models where the channels are allowed to produce the same output word as long as, in each channel, different errors occur (that is, the errors correspond to different insertion vectors). Our objective is to determine the number of channels N required to uniquely recover the transmitted word x under these conditions. We present several results in this direction, some of which are optimal.

In this article, we study the cardinality of the intersection of multiple q-ary Hamming balls for q ≥ 3. The problem has previously been studied in the binary case and for two balls in the case of q ≥ 3. When each ball has radius t and they are centered at words of a set S, we present a link between the asymptotic size of the cardinality and the center of the set S. For exactly three balls, we consider the largest and smallest possible intersection sizes and possible sets S leading to them. The intersections of Hamming balls have been the focus of multiple studies recently, due to their connections to Levenshtein’s sequence reconstruction problem and DNA memory systems, where the information is stored into DNA strands. The case with q = 4 is especially important for applications related to DNA due to the four nucleotides of DNA.

The problem of storing large amounts of information safely for a long period of time has become essential. One of the most promising new data storage mediums are the polymer-based data storage systems, like the DNA-storage system. These storage systems are highly durable and they consume very little energy to store the data. When information is retrieved from a storage, however, several different types of errors may occur in the process. It is known that the Levenshtein's sequence reconstruction framework is well-suited to overcome such errors and to retrieve the original information. Many of the previous results regarding Levenshtein's sequence reconstruction method are so far given only for the binary alphabet. However, larger alphabets are natural for the polymer-based data storage. For example, the quaternary alphabet is suitable for DNA-storage due to the four amino-acids in DNA. The results for larger alphabets often require, as we will see in this work, different and more complicated techniques compared to the binary case. Moreover, we show that an increase in the alphabet size makes some error types behave rather surprisingly.

In the Levenshtein’s sequence reconstruction problem a codeword is transmitted throughNchannels and in each channel a set of errors is introduced to the transmitted word. In previous works, the restriction that each channel provides a unique output word has been essential. In this work, we assume only that each channel introduces a unique set of errors to the transmitted word and hence, some output words can also be identical. As we will discuss, this interpretation is both natural and useful for deletion and insertion errors. We give properties, techniques and (optimal) results for this situation. Quaternary alphabets are relevant due to applications related to DNA-memories. Hence, we introduce an efficient Las Vegas style decoding algorithm for simultaneous insertion, deletion and substitution errors in q-ary Hamming spaces forq≥ 4.

A metric basis in a graph G is a smallest possible set S of vertices of G, with the property that any two vertices of G are uniquely recognized by using a vector of distances to the vertices in S. A strong metric basis is a variant of metric basis that represents a smallest possible set S′ of vertices of G such that any two vertices x,y of G are uniquely recognized by a vertex v∈S′ by using either a shortest x−v path that contains y, or a shortest y−v path that contains x. Given a graph G, there exist sometimes some vertices of G such that they forcedly belong to every metric basis or to every strong metric basis of G. Such vertices are called (resp. strong) basis forced vertices in G. It is natural to consider finding them, in order to find a (strong) metric basis in a graph. However, deciding about the existence of these vertices in arbitrary graphs is in general an NP-hard problem, which makes desirable the problem of searching for (strong) basis forced vertices in special graph classes. This article centres the attention in the class of unicyclic graphs. It is known that a unicyclic graph can have at most two basis forced vertices. In this sense, several results aimed to classify the unicyclic graphs according to the number of basis forced vertices they have are given in this work. On the other hand, with respect to the strong metric bases, it is proved in this work that unicyclic graphs can have as many strong basis forced vertices as we would require. Moreover, some characterizations of the unicyclic graphs concerning the existence or not of such vertices are given in the exposition as well.

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.

In the paper, the Levenshtein’s sequence reconstruction problem is considered in the case where the transmitted words are chosen from ane-error-correcting code, at mosttsubstitution errors occur in each of theNchannels and the decoder outputs a list of lengthL. Previously, whent=e+ ℓ and the transmitted word is long enough, the numbers of required channels were determined forL= 1, 2 and ℓ+1. Here we determine the exact number of channels in the casesL= 3,4,..., ℓ. This also provides the size of the largest intersection ofLballs of radiust(with respect to substitutions) centered at the words with mutual Hamming distances at least 2e+ 1. Furthermore, with the aid of covering codes, we also consider the list sizes in the cases where the lengthnis rather small (improving previously known results). After that we study how much we can decrease the number of required channels when we use list-decoding codes. Finally, the majority algorithm is discussed for decoding in a probabilistic set-up; in particular, we show that the output word of the decoder can be verified to be the transmitted one with high probability.

In this paper, we consider Levenshtein’s sequence reconstruction problem in which the same codeword is transmitted through N channels each introducing a different set of errors to the transmitted word. In previous works, it has been assumed that each channel provides a unique output word while we assume that each channel introduces a unique set of errors to the transmitted word and hence some output words can be identical. This property seems natural and we also give several results for this problem. Moreover, we also extend optimal decoding algorithm for substitution errors in binary Hamming space to q-ary Hamming spaces. Especially, quaternary Hamming spaces are relevant due to applications related to DNA-memories. Hence, we introduce an efficient Las Vegas decoding algorithm for simultaneous insertion, deletion and substitution errors in quaternary Hamming spaces.

In the paper, the Levenshtein’s sequence reconstruction problem is considered in the case where at most t substitution errors occur in each of the N channels and the decoder outputs a list of length at most ℒ. Moreover, it is assumed that the transmitted words are chosen from an e-error-correcting code C (⊆ {0, 1}n). Previously, when t = e + ℓ and the length n of the transmitted word is large enough, the exact numbers of required channels is determined for ℒ = 1, 2 and ℓ + 1. Here we determine the number of channels in the cases ℒ = 3, 4,…, ℓ. Furthermore, with the aid of covering codes, we also consider the list sizes in the cases where the length n is rather small. Finally, the majority algorithm is discussed for decoding; in particular, we demonstrate that with high probability a decoder based on it, is verifiably successful, i.e., outputs a list (sometimes even of size one) such that it verifiably contains the transmitted word.

A set R⊆V(G) is a resolving set of a graph G if for all distinct vertices v,u∈V(G) there exists an element r∈R such that d(r,v)≠d(r,u). The metric dimension dim(G) of the graph G is the cardinality of a smallest 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.

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 ⊆ \mathbb F2nhas error-correcting capability e, we write t=e+l, (l≥ 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 boundl+1 on the list size for large enough n provided that we have a sufficient number of channels. We also show that the boundl+1 is the best possible. Most of our other new results rely on constant weight codes.

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 ⊆ F2nhas error-correcting capability e, we write t = e + ℓ, (ℓ ≥ 1). In this paper, we provide new bounds on the size of the list. In particular, we give using the Sauer-Shelah lemma the upper bound ℓ + 1 on the list size for large enough n provided that we have a sufficient number of channels. We also show that the bound ℓ + 1 is the best possible.

A subset S of vertices is a resolving set in a graph if every vertex has a unique array of distances to the vertices of S. Consequently, we can locate any vertex of the graph with the aid of the distance arrays. The problem of finding the smallest cardinality of a resolving set in a graph has been widely studied over the years. In this paper, we consider sets S which can locate several, say up to ℓ, vertices in a graph. These sets are called {ℓ}-resolving sets and the smallest cardinality of such a set is the {ℓ}-metric dimension of the graph. In this paper, we will give the {ℓ}-metric dimensions for trees and king grids. We will show that there are certain vertices that necessarily belong to an {ℓ}-resolving set. Moreover, we will classify all graphs whose {ℓ}-metric dimension equals ℓ.

In this paper, we introduce t-revealing codes in the binary Hamming space Fn. Let C ⊆ Fnbe a code and denote by It{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 It(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.

Information retrieval in associative memories was considered recently by Yaakobi and Bruck. In their model, a stored information unit is retrieved using input clues. In this paper, we study the problem where at most s (s ≥ 0) of the received input clues can be false and we still want to determine t he sought information unit uniquely. We use a coding theoretical approach to estimate the maximum number of stored information units with respect to a given s. Moreover, optimal results for the problem are given, for example, in the infinite king grid. We also discuss the problem in the class of line graphs where a characterization and a connection to k-factors is given.

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 muon the maximum number of them is imposed. Of course, we would like muto be as small as possible. We consider the problem over the binary Hamming space Fnand focus on the minimum of mu, denoted by ν(n; t). Using linear reference sets, we show that ν(n; 2) ≤ 5 for any n ≥ 9. We also give infinite families of reference sets, which provide good bounds on ν(n; t) for t = 3. In addition, efficient methods are given to obtain bounds on ν(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.

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.

Abstract 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 article, we consider as sensors the set \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document} $\mathbb{Z}^2$ \end{document} where one sensor can check its neighbors within Euclidean distance r. We construct tolerant identifying codes in this network that are robust against some changes in the neighborhood monitored by each sensor. We give bounds for the smallest density of a tolerant identifying code for general values of r. We also provide infinite families of values r with optimal such codes and study the case of small values of r. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. Their original motivation for studying these codes comes from fault diagnosis in multiprocessor systems. Recently, other applications such as locating objects in sensor networks have been proposed. We define an r-identifying code in a graph G = (V, E) as a subset C ⊆ V such that for each u ∈ V the intersection of C and the ball of radius r centered at u is nonempty and unique. Since the seminal paper on the subject, determining the smallest densities of identifying codes in various infinite grids has been one of the essential problems in the field. In this paper, we consider 2-identifying codes in the infinite square and hexagonal grids. Previously, it has been shown that there exists a 2-identifying code in the square grid with density 5/29 ≈ 0.172 and that there are no 2-identifying codes with density smaller than 3/20 = 0.15. Recently, the lower bound has been improved to 6/37 ≈ 0.162 by Martin and Stanton (2010). We further improve the lower bound by showing that there are no 2-identifying codes in the square grid with density smaller than 6/35 ≈ 0.171. Moreover, there exists a 2-identifying code in the hexagonal grid with density 4/19 ≈ 0.211. Currently, the best known lower bound for this case is 1/5 = 0.2 by Martin and Stanton (2010). We improve this lower bound to 4/19, i.e. show that the construction with density 4/19 is optimal.

Karpovsky, Chakrabarty and Levitin introduced identifying codes, which can be applied, for example, to locating objects in sensor networks. In this paper, the underlying structure is Z2where one sensor can check its neighbours within Euclidean distance r. We construct 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 such an identifying code for general values of r. We also provide infinite families of values r with optimal such codes and study the case of small values of r.

In this paper, we consider identifying codes in binary Hamming spaces Fn. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks. Let a code C ¿ Fn. For any set of words X ¿ Fn, denote by Ir(X) = Ir(C; X) the set of codewords within distance r from at least one x ¿ X. Now a code C ¿ Fnis called (r, ¿ ¿)-identifying if the sets Ir(X) are distinct for all X ¿ Fnof size at most ¿. Let us denote by Mr(¿¿)(n) the smallest possible cardinality of an (r, ¿ ¿)-identifying code. In 2002, Honkala and Lobstein showed for ¿ = 1 that limn¿¿1/n log2Mr(¿¿)(n) = 1 - h(¿) where r = [¿n], ¿ ¿ (0, 1) and h(x) is the binary entropy function. In this paper, we prove that this result holds for any fixed ¿ ¿ 1 when ¿ ¿ (0, 1/2). We also show that Mr(¿¿)(n) = O(n3/2) for every fixed ¿ and r slightly less than n/2, and give an explicit construction of small (r, ¿ 2)-identifying codes for r = [n/2] - 1.

The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. Their motivation for identification came from finding malfunctioning processors in multiprocessor systems. Besides that identifying codes can also be applied to sensor networks. In this paper we consider identifying codes in Hamming spaces. We first concentrate on improving the lower bounds on codes which identify words within distance r > 1. These improvements are achieved using a new approach. Then we proceed by introducing new lower bounds on codes identifying sets of words. Constructions for such codes with the best known cardinalities are also given.

In binary Hamming spaces, we construct new 1- identifying codes which improve on previously known upper bounds on the cardinalities of 1-identifying codes for many lengths when n ges 10. We also construct tau-identifying codes using the direct sum of tau codes that are 1-identifying.

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\geq 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.

The motivation for identifying codes comes from maintenance of multiprocessor architectures. In this paper, we give infinite families of optimal edge-robust identifying codes and vertex-robust identifying codes in binary Hamming spaces.

It is shown that in the infinite square grid the density of every $(r, \leq 2)$-identifying code is at least 1/8 and that there exists a sequence $C_r$ of $(r, \leq 2)$-identifying codes such that the density of C r tends to 1/8 when $r \rightarrow \infty$. In the infinite triangular grid a sequence $C'_r$ of $(r, \leq 2)$-identifying codes is given such that the density of $C'_r$ tends to 0 when $r \rightarrow \infty$.

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).

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.

In this paper we estimate covering radius when dual distance is known. We derive new bounds on covering radii of linear codes. A bound for self-complementary codes is also presented. The improvements of these bounds on the known results are based on the knowledge of the cardinality of constant weight codes and on the behavior of Hahn polynomials and discrete Chebyshev polynomials.

The covering radius of a code tells us how far in the sense of Hamming distance an arbitrary word of the ambient space can be from the code. For a few decades this parameter has been widely studied. We estimate the covering ratios of a code when the dual distance is known. We derive a new bound on covering radii of linear codes. It improves essentially on the previously known estimates in a certain wide range. We also study asymptotic bounds on the cardinality of constant weight codes.

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).