Upper bounds for binary identifying codes

被引:6
作者
Exoo, Geoffrey [3 ]
Junnila, Ville [2 ]
Laihonen, Tero [1 ]
Ranto, Sanna [1 ]
机构
[1] Univ Turku, Dept Math, Turku 20014, Finland
[2] Univ Turku, Turku Ctr Comp Sci TUCS, Turku 20014, Finland
[3] Indiana State Univ, Dept Math & Comp Sci, Terre Haute, IN 47809 USA
基金
芬兰科学院;
关键词
Identifying codes; Hamming space; Locating-dominating codes; Direct sum; VERTICES; GRAPHS; SETS;
D O I
10.1016/j.aam.2008.06.004
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A nonempty set of words in a binary Hamming space F-n is called an r-identifying code if for every word the set of codewords within distance r from it is unique and nonempty. The smallest possible cardinality of an r-identifying code is denoted by M-r(n). In this paper, we consider questions closely related to the open problem whether Mt+r(n + m) <= M-t(m)M-r(n) is true. For example, we show results like M1+r(n + m) <= 4M(1)(m)M-r(n), which improve previously known bounds. We also consider codes which identify sets of words of size at most l. The smallest cardinality of such a code is denoted by M-r((<= l)) (n). we prove that M-r+1((<= l)) (n + m) <= M-r((<= l)) (n)M-t((<= l)) (m) is true for all l >= r + 3 when r >= 1 and t = 1. We also obtain a result M-1 (n + 1) <= (2 + epsilon(n))M-1(n) where epsilon(n) -> 0 when n -> infinity. This bound is related to the conjecture M-1 (n + 1) <= 2M(1) (n). Moreover. we give constructions for the best known 1-identifying codes of certain lengths. (C) 2008 Elsevier Inc. All rights reserved.
引用
收藏
页码:277 / 289
页数:13
相关论文
共 50 条
[41]   Sphere coverings and identifying codes [J].
Auger, David ;
Cohen, Gerard ;
Mesnager, Sihem .
DESIGNS CODES AND CRYPTOGRAPHY, 2014, 70 (1-2) :3-7
[42]   Identifying codes and covering problems [J].
Laifenfeld, Moshe ;
Trachtenberg, Ari .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2008, 54 (09) :3929-3950
[43]   Periodicity of identifying codes in strips [J].
Jiang, Minghui .
INFORMATION PROCESSING LETTERS, 2018, 135 :77-84
[44]   Identifying codes for generalized quadrangles [J].
Tamás Héger ;
György Kiss ;
Anamari Nakić ;
Leo Storme .
Journal of Geometry, 2024, 115
[45]   Sphere coverings and identifying codes [J].
David Auger ;
Gérard Cohen ;
Sihem Mesnager .
Designs, Codes and Cryptography, 2014, 70 :3-7
[46]   Characterizing Extremal Digraphs for Identifying Codes and Extremal Cases of Bondy's Theorem on Induced Subsets [J].
Foucaud, Florent ;
Naserasr, Reza ;
Parreau, Aline .
GRAPHS AND COMBINATORICS, 2013, 29 (03) :463-473
[47]   Identifying codes for generalized quadrangles [J].
Heger, Tamas ;
Kiss, Gyoergy ;
Nakic, Anamari ;
Storme, Leo .
JOURNAL OF GEOMETRY, 2024, 115 (01)
[48]   Upper Bounds for α-Domination Parameters [J].
Gagarin, Andrei ;
Poghosyan, Anush ;
Zverovich, Vadim .
GRAPHS AND COMBINATORICS, 2009, 25 (04) :513-520
[49]   Upper Bounds on Distance Energy [J].
Das, Kinkar Chandra ;
Gutman, Ivan .
MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY, 2021, 86 (03) :611-620
[50]   Upper Bounds for Randic Spread [J].
Gomes, Helena ;
Martins, Enide ;
Robbiano, Maria ;
San Martin, Bernardo .
MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY, 2014, 72 (01) :267-278