Optimal local identifying and local locating-dominating codes
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913010592776192 |
|---|---|
| author | Herva, Pyry Laihonen, Tero Lehtilä, Tuomo |
| author_facet | Herva, Pyry Laihonen, Tero Lehtilä, Tuomo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_13351 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Optimal local identifying and local locating-dominating codes Herva, Pyry Laihonen, Tero Lehtilä, Tuomo Discrete Mathematics Combinatorics 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. |
| title | Optimal local identifying and local locating-dominating codes |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2302.13351 |