A1 Refereed original research article in a scientific journal
On the density of (1,≤ℓ)-locating-dominating codes in the infinite square grid; 
Authors: Das, Soura Sena; Lehtilä, Tuomo; Nandi, Soumen; Sen, Sagnik
Publisher: Elsevier BV
Publication year: 2026
Journal: Discrete Mathematics
Article number: 115311
Volume: 349
ISSN: 0012-365X
eISSN: 1872-681X
DOI: https://doi.org/10.1016/j.disc.2026.115311
Publication's open availability at the time of reporting: Open Access
Publication channel's open availability : Partially Open Access publication channel
Web address : https://doi.org/10.1016/j.disc.2026.115311
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/526944609
Self-archived copy's licence: CC BY
Self-archived copy's version: Publisher`s PDF
Given a simple graph G, let Br(v) be the set of vertices at a distance of at most r from v.
Avertex subset C is an (r,≤ℓ)-locating-dominating code of type A or (r,≤ℓ)-LDA code if
the sets Ir(F) = Br(F)∩C are distinct for all vertex subsets F ⊆ V(G) of size at most ℓ that
share the same vertices in C. Similarly, C is referred to as an (r,≤ ℓ)-locating-dominating
code of type B or (r,≤ℓ)-LDB code if the identifying sets Ir(F) are distinct for all vertex
subsets F ⊆ V(G)\C of size at most ℓ. In this article, we present optimal (with respect to
density) (1,≤ ℓ)-LDA and (1,≤ ℓ + 1)-LDB codes in the infinite square grid for all ℓ ≥ 2.
For (1,≤ 2)-LDB codes in infinite square grid, we show that the optimal code will have
density between [2/5, 5/11].
Downloadable publication This is an electronic reprint of the original article. |  |
Funding information in the publication:
This work is partially supported by the IFCAM project “Applications of graph homomorphisms” (MA/IFCAM/18/39), “NBHM/RP-8(2020)/Fresh”, SERB-MATRICS “Oriented chromatic and clique number of planar graphs” (MTR/2021/000858). The research of Tuomo Lehtilä was supported by the Finnish Cultural Foundation and Research Council of Finland grants 338797 and 358718.
