A1 Refereed original research article in a scientific journal
Locating vertices using codes
Authors: Exoo G, Junnila V, Laihonen T, Ranto S
Publisher: Utilitas Mathematica Publishing Inc.
Publication year: 2008
Journal: Congressus Numerantium
Volume: 191
First page : 143
Last page: 159
Number of pages: 17
Abstract
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.
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.
UTU Research Portal