Search

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.

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

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 + l, (l ≥ 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 l + 1 on the list size for large enough n provided that we have a sufficient number of channels. We also show that the bound l + 1 is the best possible.

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.

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.