Fake base stations (FBSs) can carry out attacks against mobile devices and user equipment (UE). We tackle the problem of localizing an FBS after its existence has been detected. Karaçay et al. (2021) have presented a localization method based on the values of the Reference Signal Received Power (RSRP), reported in the standardized measurement reports of the 3rd Generation Partnership Project (3GPP) and sent by the UEs. We show that the method they have proposed fails if the FBS uses a directional antenna (instead of an omnidirectional antenna). The localization method by Karaçay et al. is based on half-planes. We propose a new method that localizes FBSs using a directional antenna by first employing a half-plane method and then applying a method based on convex hulls. Our tests for the new method on data derived from Network Simulator 3 (ns-3) show that it significantly outperforms the previous method for a directional FBS antenna.

We study a generalization of the problem of reconstructing strings from their substring compositions first proposed by Acharya et al. in 2015. This problem is linked to information retrieval from polymer-based data storage systems where the information is read from polymers with tandem mass (MS/MS) spectrometers. Previously the problem has been studied when the polymers are strings/paths. However, polymers allow different structures, which motivates the more general problem of reconstructing graphs from their connected subgraphs compositions. We present some graph classes for which graphs are reconstructable. In particular, we present an infinite subclass of subdivided stars which are reconstructable, allow storing more information than strings, have a simple reconstruction algorithm and structure. Besides positive results, we also give some graph classes where a large number of non-isomorphic labelings yield the same composition multisets.

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.

The dominating set problem (DSP) is one of the most famous problems in combinatorial optimization. It is defined as follows. For a given graph G=(V,E), a dominating set of G is a subset S⊆V such that every vertex in V∖S is adjacent to at least one vertex in S. Furthermore, the DSP is the problem of finding a minimum-size dominating set and the corresponding minimum size, the domination number of G. In this, work we investigate a variant of the DSP, the super dominating set problem (SDSP), which has attracted much attention during the last years. A dominating set S is called a super dominating set of G, if for every vertex u∈S¯=V∖S, there exists a v∈S such that N(v)∩S¯=N(v)∖S={u}. Analogously, the SDSP is to find a minimum-size super dominating set, and the corresponding minimum size, the super domination number of G. The decision variants of both the DSP and the SDSP have been shown to be NP-hard. In this paper, we present tight bounds for the super domination number of the neighbourhood corona product, r-clique sum, and the Hajós sum of two graphs. Additionally, we present infinite families of graphs attaining our bounds. Finally, we give the exact number of minimum size super dominating sets for some graph classes. In particular, the number of super dominating sets for cycles has quite surprising properties as it varies between values of the set {4,n,2n,5n2−10n8} based on nmod4.

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.

An identifying code of a closed-twin-free graph G is a set S of vertices of G such that any two vertices in G have a distinct intersection between their closed neighborhoods and S. It was conjectured in [F. Foucaud, R. Klasing, A. Kosowski, A. Raspaud. On the size of identifying codes in triangle-free graphs. Discrete Applied Mathematics, 2012] that there exists an absolute constant c such that for every connected graph G of order n and maximum degree ∆, G admits an identifying code of size at most ∆-1/∆n + c. We provide significant support for this conjecture by proving it for the class of all bipartite graphs that do not contain any pairs of open-twins of degree at least 2. In particular, this class of bipartite graphs contains all trees and more generally, all bipartite graphs without 4-cycles. Moreover, our proof allows us to precisely determine the constant c for the considered class, and the list of graphs needing c ≥ 0. For ∆ = 2 (the graph is a path or a cycle), it is long known that c = 3/2 suffices. For connected graphs in the considered graph class, for each ∆ ≥ 3, we show that c = 1/∆ ≤ 1/3 suffices and that c is required to be positive only for a finite number of trees. In particular, for ∆ = 3, there are 12 trees with diameter at most 6 with a positive constant c and, for each ∆ ≥ 4, the only tree with positive constant c is the ∆-star. Our proof is based on induction and utilizes recent results from [F. Foucaud, T. Lehtilä. Revisiting and improving upper bounds for identifying codes. SIAM Journal on Discrete Mathematics, 2022].

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.

An identifying code $C$ of a graph $G$ is a dominating set of $G$ such that any two distinct vertices of $G$ have distinct closed neighborhoods within $C$. These codes have been widely studied for over two decades. We give an improvement over all the best known upper bounds, some of which have stood for over 20 years, for identifying codes in trees, proving the upper bound of $(n+\ell)/2$, where $n$ is the order and $\ell$ is the number of leaves (pendant vertices) of the graph. In addition to being an improvement in size, the new upper bound is also an improvement in generality, as it actually holds for bipartite graphs having no twins (pairs of vertices with the same closed or open neighborhood) of degree 2 or greater. We also show that the bound is tight for an infinite class of graphs and that there are several structurally different families of trees attaining the bound. We then use our bound to derive a tight upper bound of $2n/3$ for twin-free bipartite graphs of order $n$ and characterize the extremal examples as 2-corona graphs of bipartite graphs. This is the best possible, as there exist twin-free graphs, and trees with twins, that need $n-1$ vertices in any of their identifying codes. We also generalize the existing upper bound of $5n/7$ for graphs of order $n$ and girth at least 5 when there are no leaves to the upper bound $\frac{5n+2\ell}{7}$ when leaves are allowed. This is tight for the 7-cycle $C_7$ and for all stars.

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.

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.