Locating vertices using codes



: Exoo G, Junnila V, Laihonen T, Ranto S

Publisher: Utilitas Mathematica Publishing Inc.

: 2008

: Congressus Numerantium

: 191

: 143

: 159

: 17


A nonempty subset of the vertices (called words) of a binary n-dimensional hypercube is called an r-locating-dominating code if for every non-codeword the set of codewords within distance r from it is nonempty and different. An r-locating-dominating code is r-identifying if the condition holds for all words (not only
non-codewords). The smallest possible cardinality of an r-identifying code of dimension n is denoted by M_r(n). It is an open problem whether M_{r+s}(n+m)\le  M_r(n)M_s(m) holds. We show that when m is relatively small compared to n the
conjecture holds. We also prove similar results for the cardinalities of codes identifying sets of vertices. We give constructions and lower bounds for r-locating-dominating codes.



Last updated on 2024-26-11 at 21:18