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 rid and the king grid. We prove that seven out of eight of our constructions have optimal densities.
翻译：我们为每个正整数$引入了两个新类别的图形覆盖代码。 这些新代码被称为本地美元识别代码和本地美元分配定位代码, 分别来自美元识别代码和美元分配定位代码。 我们研究了二进制超立方体中最佳本地1识别代码和本地1定位代码的大小。 我们获得的下层和上层界限过于紧凑。 这些界限加起来表明,将覆盖代码转换为本地1识别代码的成本微不足道。 对于一些小的美元最佳建筑, 也获得了。 此外, 上层界限是通过线性代码构造获得的。 此外, 我们研究无限方格、六边形网、三角形和王网中最佳1位代码的密度。 我们证明, 我们8个建筑中有7个具有最佳密度。</s>
相关内容
微信扫码咨询专知VIP会员