On the density of (1,≤ℓ)-locating-dominating codes in the infinite square grid;
: Das, Soura Sena; Lehtilä, Tuomo; Nandi, Soumen; Sen, Sagnik
Publisher: Elsevier BV
: 2026
Discrete Mathematics
: 115311
: 349
: 0012-365X
: 1872-681X
DOI: https://doi.org/10.1016/j.disc.2026.115311
: https://doi.org/10.1016/j.disc.2026.115311
: https://research.utu.fi/converis/portal/detail/Publication/526944609
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].
:
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.
