A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Improved lower bound for locating-dominating codes in binary Hamming spaces
Tekijät: Junnila Ville, Laihonen Tero, Lehtilä Tuomo
Kustantaja: SPRINGER
Julkaisuvuosi: 2022
Journal: Designs, Codes and Cryptography
Tietokannassa oleva lehden nimi: DESIGNS CODES AND CRYPTOGRAPHY
Lehden akronyymi: DESIGN CODE CRYPTOGR
Vuosikerta: 90
Aloitussivu: 67
Lopetussivu: 85
Sivujen määrä: 19
ISSN: 0925-1022
eISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-021-00963-8
Verkko-osoite: https://link.springer.com/article/10.1007/s10623-021-00963-8
Preprintin osoite: https://arxiv.org/abs/2102.05537
Tiivistelmä
In this article, we study locating-dominating codes in binary Hamming spaces F-n. Locating-dominating codes have been widely studied since their introduction in 1980s by Slater and Rall. They are dominating sets suitable for distinguishing vertices in graphs. Dominating sets as well as locating-dominating codes have been studied in Hamming spaces in multiple articles. Previously, Honkala et al. (Discret Math Theor Comput Sci 6(2):265, 2004) have presented a lower bound for locating-dominating codes in binary Hamming spaces. In this article, we improve the lower bound for all values n >= 10. In particular, when n = 11, we manage to improve the previous lower bound from 309 to 317. This value is very close to the current best known upper bound of 320.
In this article, we study locating-dominating codes in binary Hamming spaces F-n. Locating-dominating codes have been widely studied since their introduction in 1980s by Slater and Rall. They are dominating sets suitable for distinguishing vertices in graphs. Dominating sets as well as locating-dominating codes have been studied in Hamming spaces in multiple articles. Previously, Honkala et al. (Discret Math Theor Comput Sci 6(2):265, 2004) have presented a lower bound for locating-dominating codes in binary Hamming spaces. In this article, we improve the lower bound for all values n >= 10. In particular, when n = 11, we manage to improve the previous lower bound from 309 to 317. This value is very close to the current best known upper bound of 320.
Turun yliopiston Tutkimustietojärjestelmän portaali