A1 Refereed original research article in a scientific journal

Improved lower bound for locating-dominating codes in binary Hamming spaces




AuthorsJunnila Ville, Laihonen Tero, Lehtilä Tuomo

PublisherSPRINGER

Publication year2022

JournalDesigns, Codes and Cryptography

Journal name in sourceDESIGNS CODES AND CRYPTOGRAPHY

Journal acronymDESIGN CODE CRYPTOGR

Volume90

First page 67

Last page85

Number of pages19

ISSN0925-1022

eISSN1573-7586

DOIhttps://doi.org/10.1007/s10623-021-00963-8(external)

Web address https://link.springer.com/article/10.1007/s10623-021-00963-8(external)

Preprint addresshttps://arxiv.org/abs/2102.05537(external)


Abstract
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.



Last updated on 2024-26-11 at 23:12